确定字符串是否是另一个的排列
给定两个字符串str1,str2, 判断str1是否是str2字符的一个排列。
例子
is_permutation('Hello','Hlleo') -> True
is_permutation('Hello','lleho') -> False
is_permutation("cat", "catt") -> False
is_permutation("world", "dlwor") -> True假设
- 字符串字符仅由ascii字符组成
- 大小写敏感
tips
- 对字符串进行排序
- 统计每个字符出现的次数
解法
解法1：
def is_permutation(str1, str2):
if str1 is None or str2 is None:
return False
return sorted(str1) == sorted(str2)性能：
- 时间复杂度
O(nlogn)，因为使用了排序 - 空间复杂度
O(n)
关键点：
sorted函数:将字符串按照其中字符字典序排序并返回排序后的字符的list
解法2:
def is_permutation(str1, str2):
if str1 is None or str2 is None:
return False
if len(str1) != len(str2):
return False
unique_counts1 = {}
unique_counts2 = {}
for char in str1:
unique_counts1[char] = unique_counts1.get(char,0) + 1
for char in str2:
unique_counts2[char] = unique_counts2.get(char,0) + 1
return unique_counts1 == unique_counts2性能：
- 时间复杂度
O(n) - 空间复杂度
O(n)
关键点：
- 利用
dict统计每个字符出现的次数
解法3：
def is_permutation(str1, str2):
if str1 is None or str2 is None:
return False
if len(str1) != len(str2):
return False
from collections import Counter
counter1 = Counter(str1)
counter2 = Counter(str2)
return counter1 == counter2性能：
- 时间复杂度：
O(2n) - 空间复杂度：
O(3n)
关键点：
- 与解法二想法一样，只是使用了
Counter统计频率
解法4：
def is_permutation(str1, str2):
if str1 is None or str2 is None:
return False
if len(str1) != len(str2):
return False
str1_xor = 0
str2_xor = 0
for item in str1:
str1_xor ^= ord(item)
for item in str2:
str1_xor ^= ord(item)
return not str1_xor ^ str2_xor性能：
- 时间复杂度：O(2n)
- 空间复杂度：O(1)
关键点：
- 利用异或，相同字符异或结果为0。如果两个字符串异或结果为0的话，证明两个字符串中出现的字符和字符频率相同