问题描述
我们的目标是写一个函数，它将两个字符串做参数并返回布尔值。如果第二个字符串只是第一个的重新排列，那么返回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(n2)或O(nlogn)，因而总的时间复杂度也是O(n2)或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)的时间复杂度下就可以完成运算，这种空间换时间的方法是更为有效的。
