使用 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