問題描述

我們的目標是寫一個函數(shù)，它將兩個字符串做參數(shù)并返回布爾值。如果第二個字符串只是第一個的重新排列，那么返回True，否則返回False。例如，'apple' 和 'paple' 就返回True。'java' 和 'aavj' 也是。
我們假設(shè)兩個字符串具有相等的長度，并且他們由 26 個小寫英文字母組成。

逐個字符比較法

首先我們考慮逐個將第一個字符串中的字符與第二個字符進行比較，判斷包含關(guān)系，如果全部包含在第二個字符中

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():
    ###前三個正確結(jié)果為true，后兩個正確結(jié)果為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()

運行結(jié)果為：

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 .
----------------------------------------------

結(jié)果是正確的，查找操作的時間復(fù)雜度假設(shè)為O(n)，則總的時間復(fù)雜度為O(n^2)。

先排序后比較的方法

兩個字符串如果能夠返回True，那么它們在字符級別各自排序后應(yīng)該是相同的字符串。

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():
    ###前三個正確結(jié)果為true，后兩個正確結(jié)果為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()

運行結(jié)果如下：

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 .
----------------------------------------------

排序操作的時間復(fù)雜度通常為O(n^{2)或O(nlogn)，因而總的時間復(fù)雜度也是O(n}2)或O(nlogn)。這與第一種方法的時間復(fù)雜度基本相當(dāng)。

先計數(shù)后比較法

我們以26個計數(shù)單位來計數(shù)兩個字符串中字符出現(xiàn)的次數(shù)，比較是否相同。

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 ##計數(shù)用數(shù)組
    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():
    ###前三個正確結(jié)果為true，后兩個正確結(jié)果為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("----------------------------------------------")
    
    ###計數(shù)后比較法
    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()

運行結(jié)果如下：

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)的時間復(fù)雜度下就可以完成運算，這種空間換時間的方法是更為有效的。