难度: Easy
给定两个由小写字母组成的字符串 s1
和 s2
,请编写一个程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串。
示例 1:
输入:s1
= "abc",s2
= "bca" 输出: true
示例 2:
输入:s1
= "abc",s2
= "bad" 输出: false
说明:
0 <= len(s1) <= 100
0 <= len(s2) <= 100
难度: Easy
给定两个由小写字母组成的字符串 s1
和 s2
,请编写一个程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串。
示例 1:
输入:s1
= "abc",s2
= "bca" 输出: true
示例 2:
输入:s1
= "abc",s2
= "bad" 输出: false
说明:
0 <= len(s1) <= 100
0 <= len(s2) <= 100
运行时间: 16 ms
内存: 16.0 MB
class Solution: def CheckPermutation(self, s1: str, s2: str) -> bool: if len(s1)!=len(s2): return False sorted_str1=sorted(s1) sorted_str2=sorted(s2) if sorted_str1 == sorted_str2: return True return False
此题解的思路是首先检查两个字符串的长度是否相同。如果长度不同,则直接返回False,因为不同长度的字符串不可能互为字符重排。如果长度相同,则将两个字符串分别排序,并比较排序后的字符串是否相等。如果排序后的字符串相同,则说明一个字符串可以通过重新排列成为另一个字符串,返回True;否则返回False。这种方法利用了排序来简化字符出现次数的比较。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution: def CheckPermutation(self, s1: str, s2: str) -> bool: # 如果两字符串长度不同,直接返回False if len(s1) != len(s2): return False # 对两个字符串分别排序 sorted_str1 = sorted(s1) sorted_str2 = sorted(s2) # 比较排序后的字符串是否相等 if sorted_str1 == sorted_str2: return True # 如果排序后的字符串不相等,返回False return False
选择排序两个字符串然后比较,主要是因为这种方法实现简单且直观。对字符串排序然后比较是否相等是一种直接的方式来检查两个字符串是否有相同的字符集和字符频率。虽然直接计数每个字符的出现次数(使用哈希表或数组)通常在时间复杂度上更优(O(n) vs O(n log n)),但排序方法在代码实现上更为简洁,特别是在使用现有的排序和比较函数库时。此外,对于较小的输入大小,这种方法的性能差异对于总体运行时间的影响不大。
排序算法的时间复杂度通常是O(n log n),其中n是字符串的长度。虽然这种排序后比较的方法并非在所有情况下都是最优的,尤其是对于非常长的字符串,直接使用字符计数的方法(哈希表或固定大小的数组来统计每个字符的频率,时间复杂度为O(n))在理论上更快更优。然而,对于较短的字符串或者当实现简便性比算法的绝对性能更重要时,排序方法可以是一个合理的选择。
如果字符串包含非ASCII字符,排序和比较的基本原理不变,但需要确保排序算法和比较逻辑能够正确处理Unicode或其他字符集的字符。在Python中,内置的排序函数已经可以很好地处理Unicode字符,因为它基于Unicode码点来比较字符。因此,即使是包含非ASCII字符的字符串,使用Python的sorted()函数仍然可以正确排序。然而,在其他一些编程环境中,可能需要特别注意字符编码和比较逻辑,确保字符排序和比较操作的正确性。