使用 Python 檢查兩個字串是否為變位詞

Vaibhav Vaibhav 2023年1月30日 2022年5月17日
  1. 在 Python 中使用排序檢查兩個字串是否為變位詞
  2. 使用 Python 中的頻率詞典檢查兩個字串是否為變位詞
使用 Python 檢查兩個字串是否為變位詞

變位詞是通過重新排列其他單詞的字母而形成的單詞。

例如,racecarelistensilentfriedfiredkneekeen 是一些變位詞對。dadbadapplemangohelloworld 不是變位詞。

使用程式語言,我們可以快速檢查兩個字串是否互為變位詞。

本文將展示如何使用 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
Vaibhav Vaibhav avatar Vaibhav Vaibhav avatar

Vaibhav is an artificial intelligence and cloud computing stan. He likes to build end-to-end full-stack web and mobile applications. Besides computer science and technology, he loves playing cricket and badminton, going on bike rides, and doodling.

LinkedIn GitHub

相關文章 - Python String