問題描述
我們的目標(biāo)是寫一個(gè)函數(shù)敞斋，它將兩個(gè)字符串做參數(shù)并返回布爾值截汪。如果第二個(gè)字符串只是第一個(gè)的重新排列，那么返回True植捎，否則返回False衙解。例如，'apple' 和 'paple' 就返回True焰枢。'java' 和 'aavj' 也是蚓峦。
我們假設(shè)兩個(gè)字符串具有相等的長(zhǎng)度，并且他們由 26 個(gè)小寫英文字母組成济锄。
逐個(gè)字符比較法
首先我們考慮逐個(gè)將第一個(gè)字符串中的字符與第二個(gè)字符進(jìn)行比較枫匾，判斷包含關(guān)系，如果全部包含在第二個(gè)字符中
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():
###前三個(gè)正確結(jié)果為true拟淮，后兩個(gè)正確結(jié)果為false干茉。
List1 = ['apple','pear','reading','swimming','commic']
List2 = ['paple','aerp','ndrgiea','mwgswini','imiucm']
###逐個(gè)比較法
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()
運(yùn)行結(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é)果是正確的，查找操作的時(shí)間復(fù)雜度假設(shè)為O(n)很泊，則總的時(shí)間復(fù)雜度為O(n^2)角虫。
先排序后比較的方法
兩個(gè)字符串如果能夠返回True沾谓，那么它們?cè)谧址?jí)別各自排序后應(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():
###前三個(gè)正確結(jié)果為true戳鹅，后兩個(gè)正確結(jié)果為false均驶。
List1 = ['apple','pear','reading','swimming','commic']
List2 = ['paple','aerp','ndrgiea','mwgswini','imiucm']
###逐個(gè)比較法
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()
運(yùn)行結(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 .
----------------------------------------------
排序操作的時(shí)間復(fù)雜度通常為O(n2)或O(nlogn)，因而總的時(shí)間復(fù)雜度也是O(n2)或O(nlogn)枫虏。這與第一種方法的時(shí)間復(fù)雜度基本相當(dāng)妇穴。
先計(jì)數(shù)后比較法
我們以26個(gè)計(jì)數(shù)單位來計(jì)數(shù)兩個(gè)字符串中字符出現(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 ##計(jì)數(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():
###前三個(gè)正確結(jié)果為true腾它，后兩個(gè)正確結(jié)果為false。
List1 = ['apple','pear','reading','swimming','commic']
List2 = ['paple','aerp','ndrgiea','mwgswini','imiucm']
###逐個(gè)比較法
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("----------------------------------------------")
###計(jì)數(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()
運(yùn)行結(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)的時(shí)間復(fù)雜度下就可以完成運(yùn)算死讹，這種空間換時(shí)間的方法是更為有效的瞒滴。
