【Python】（二）第二个字符串是否只是第一个的重新排列？

问题描述

我们的目标是写一个函数，它将两个字符串做参数并返回布尔值。如果第二个字符串只是第一个的重新排列，那么返回True，否则返回False。例如，'apple' 和 'paple' 就返回True。'java' 和 'aavj' 也是。
我们假设两个字符串具有相等的长度，并且他们由 26 个小写英文字母组成。

逐个字符比较法

首先我们考虑逐个将第一个字符串中的字符与第二个字符进行比较，判断包含关系，如果全部包含在第二个字符中

def method_1(str_1, str_2):
    str_2 = list(str_2)
    pos_1 = 0
    flag_same = True
    while pos_1<len(str_1) and flag_same:
        try:
            pos_2 = str_2.index(str_1[pos_1]) ##查找操作
            str_2.pop(pos_2)
        except:
            flag_same = False
        pos_1 += 1
    return flag_same

def main():
    ###前三个正确结果为true，后两个正确结果为false。
    List1 = ['apple','pear','reading','swimming','commic']
    List2 = ['paple','aerp','ndrgiea','mwgswini','imiucm']
    
    ###逐个比较法
    for i in range(len(List1)):
        print("Sum method 1 -- %s and %s -- Result %s ."%(List1[i], List2[i], method_1(List1[i], List2[i])))

    print("----------------------------------------------")

if __name__ == "__main__":
    main()

运行结果为：

Sum method 1 -- apple and paple -- Result True .
Sum method 1 -- pear and aerp -- Result True .
Sum method 1 -- reading and ndrgiea -- Result True .
Sum method 1 -- swimming and mwgswini -- Result False .
Sum method 1 -- commic and imiucm -- Result False .
----------------------------------------------

结果是正确的，查找操作的时间复杂度假设为O(n)，则总的时间复杂度为O(n^2)。

先排序后比较的方法

两个字符串如果能够返回True，那么它们在字符级别各自排序后应该是相同的字符串。

def method_1(str_1, str_2):
    str_2 = list(str_2)
    pos_1 = 0
    flag_same = True
    while pos_1<len(str_1) and flag_same:
        try:
            pos_2 = str_2.index(str_1[pos_1]) ##查找操作
            str_2.pop(pos_2)
        except:
            flag_same = False
        pos_1 += 1
    return flag_same

def method_2(str_1, str_2):
    str_1 = list(str_1)
    str_1.sort() ##排序操作
    str_2 = list(str_2)
    str_2.sort() ##排序操作
    for i in range(len(str_1)):
        if str_1[i] != str_2[i]:
            return False
    return True

def main():
    ###前三个正确结果为true，后两个正确结果为false。
    List1 = ['apple','pear','reading','swimming','commic']
    List2 = ['paple','aerp','ndrgiea','mwgswini','imiucm']
    
    ###逐个比较法
    for i in range(len(List1)):
        print("Sum method 1 -- %s and %s -- Result %s ."%(List1[i], List2[i], method_1(List1[i], List2[i])))

    print("----------------------------------------------")
    
    ###排序后比较法
    for i in range(len(List1)):
        print("Sum method 2 -- %s and %s -- Result %s ."%(List1[i], List2[i], method_2(List1[i], List2[i])))

    print("----------------------------------------------")

if __name__ == "__main__":
    main()

运行结果如下：

Sum method 1 -- apple and paple -- Result True .
Sum method 1 -- pear and aerp -- Result True .
Sum method 1 -- reading and ndrgiea -- Result True .
Sum method 1 -- swimming and mwgswini -- Result False .
Sum method 1 -- commic and imiucm -- Result False .
----------------------------------------------
Sum method 2 -- apple and paple -- Result True .
Sum method 2 -- pear and aerp -- Result True .
Sum method 2 -- reading and ndrgiea -- Result True .
Sum method 2 -- swimming and mwgswini -- Result False .
Sum method 2 -- commic and imiucm -- Result False .
----------------------------------------------

排序操作的时间复杂度通常为O(n^{2)或O(nlogn)，因而总的时间复杂度也是O(n}2)或O(nlogn)。这与第一种方法的时间复杂度基本相当。

先计数后比较法

我们以26个计数单位来计数两个字符串中字符出现的次数，比较是否相同。

def method_1(str_1, str_2):
    str_2 = list(str_2)
    pos_1 = 0
    flag_same = True
    while pos_1<len(str_1) and flag_same:
        try:
            pos_2 = str_2.index(str_1[pos_1]) ##查找操作
            str_2.pop(pos_2)
        except:
            flag_same = False
        pos_1 += 1
    return flag_same

def method_2(str_1, str_2):
    str_1 = list(str_1)
    str_1.sort() ##排序操作
    str_2 = list(str_2)
    str_2.sort() ##排序操作
    for i in range(len(str_1)):
        if str_1[i] != str_2[i]:
            return False
    return True

def method_3(str_1, str_2):
    count_list = [0]*26 ##计数用数组
    for x in list(str_1):
        count_list[ord(x)-ord('a')] += 1
    for x in list(str_2):
        count_list[ord(x)-ord('a')] -= 1
    for x in count_list:
        if x != 0:
            return False
    return True

def main():
    ###前三个正确结果为true，后两个正确结果为false。
    List1 = ['apple','pear','reading','swimming','commic']
    List2 = ['paple','aerp','ndrgiea','mwgswini','imiucm']
    
    ###逐个比较法
    for i in range(len(List1)):
        print("Sum method 1 -- %s and %s -- Result %s ."%(List1[i], List2[i], method_1(List1[i], List2[i])))

    print("----------------------------------------------")
    
    ###排序后比较法
    for i in range(len(List1)):
        print("Sum method 2 -- %s and %s -- Result %s ."%(List1[i], List2[i], method_2(List1[i], List2[i])))

    print("----------------------------------------------")
    
    ###计数后比较法
    for i in range(len(List1)):
        print("Sum method 3 -- %s and %s -- Result %s ."%(List1[i], List2[i], method_3(List1[i], List2[i])))

if __name__ == "__main__":
    main()

运行结果如下：

Sum method 1 -- apple and paple -- Result True .
Sum method 1 -- pear and aerp -- Result True .
Sum method 1 -- reading and ndrgiea -- Result True .
Sum method 1 -- swimming and mwgswini -- Result False .
Sum method 1 -- commic and imiucm -- Result False .
----------------------------------------------
Sum method 2 -- apple and paple -- Result True .
Sum method 2 -- pear and aerp -- Result True .
Sum method 2 -- reading and ndrgiea -- Result True .
Sum method 2 -- swimming and mwgswini -- Result False .
Sum method 2 -- commic and imiucm -- Result False .
----------------------------------------------
Sum method 3 -- apple and paple -- Result True .
Sum method 3 -- pear and aerp -- Result True .
Sum method 3 -- reading and ndrgiea -- Result True .
Sum method 3 -- swimming and mwgswini -- Result False .
Sum method 3 -- commic and imiucm -- Result False .

在O(n)的时间复杂度下就可以完成运算，这种空间换时间的方法是更为有效的。