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