使用 Python 检查两个字符串是否为变位词
Vaibhav Vaibhav
2023年1月30日
2022年5月17日
变位词是通过重新排列其他单词的字母而形成的单词。
例如,race
和 care
、listen
和 silent
、fried
和 fired
、knee
和 keen
是一些变位词对。dad
和 bad
、apple
和 mango
、hello
和 world
不是变位词。
使用编程语言,我们可以快速检查两个字符串是否互为变位词。
本文将展示如何使用 Python 检查两个字符串是否为变位词。我们将讨论一些相同的方法。
在 Python 中使用排序检查两个字符串是否为变位词
要检查两个字符串是否是变位词,我们可以对两个字符串进行排序并检查它们是否相等。相同的参考下面的代码。
由于排序,代码的时间复杂度为 O(nlogn)
,空间复杂度为 O(1)
,因为我们没有存储任何值。
def check_anagram(a, b):
if a is None or b is None or len(a) != len(b):
return "Not Anagram"
return "Anagram" if sorted(a) == sorted(b) else "Not Anagram"
print(check_anagram("keen", "knee"))
print(check_anagram("race", "care"))
print(check_anagram("fried", "fired"))
print(check_anagram("apple", "paddle"))
print(check_anagram("first", "second"))
print(check_anagram(None, "second"))
print(check_anagram("first", None))
print(check_anagram(None, None))
输出:
Anagram
Anagram
Anagram
Not Anagram
Not Anagram
Not Anagram
Not Anagram
Not Anagram
使用 Python 中的频率词典检查两个字符串是否为变位词
要检查两个字符串是否是变位词,我们可以保留两个字符串中存在的字符数并比较计数。如果它们相同,这意味着这两个字符串是变位词。否则,他们不是。
相同的参考下面的代码。
以下解决方案的时间复杂度为 O(n)
,因为我们正在迭代两个字符串。将元素添加到字典并检索元素的平均时间复杂度为 O(1)
。
此外,比较具有相同键数的两个字典是 O(n)
。而且,空间复杂度是 O(n)
,因为我们要维护两个字典,而在幕后,字典使用数组来存储键和值。
def check_anagram(a, b):
if a is None or b is None or len(a) != len(b):
return "Not Anagram"
counts_a = {}
counts_b = {}
for x in a:
if x not in counts_a.keys():
counts_a[x] = 1
else:
counts_a[x] += 1
for x in b:
if x not in counts_b.keys():
counts_b[x] = 1
else:
counts_b[x] += 1
return "Anagram" if counts_a == counts_b else "Not Anagram"
print(check_anagram("keen", "knee"))
print(check_anagram("race", "care"))
print(check_anagram("fried", "fired"))
print(check_anagram("apple", "paddle"))
print(check_anagram("first", "second"))
print(check_anagram(None, "second"))
print(check_anagram("first", None))
print(check_anagram(None, None))
输出:
Anagram
Anagram
Anagram
Not Anagram
Not Anagram
Not Anagram
Not Anagram
Not Anagram
Author: Vaibhav Vaibhav