如何用Python检查两个单词是否为变位词

Question

我正在处理一个简单的问题：

• 检查两个字符串是否为异序词（anagrams）。

我已经编写了简单的代码，可以检查两个字符串例如'abcd'和'dcba'是否为异序词，但是对于更复杂的字符串如"Astronomer"和"Moon starter"我不知道该怎么办。

line1 = input('Enter the first word: ')
line2 = input('Enter the second word: ')

def deleteSpaces(s):
    s_new = s.replace(" ","")
    return s_new


def anagramSolution2(s1,s2):
    alist1 = list(deleteSpaces(s1))
    alist2 = list(deleteSpaces(s2))

    print(alist1)
    print(alist2)

    alist1.sort()
    alist2.sort()

    pos = 0
    matches = True

    while pos < len(deleteSpaces(s1)) and matches:
        if alist1[pos]==alist2[pos]:
            pos = pos + 1
        else:
            matches = False

    return matches

首先，我认为问题在于处理空格，但后来我明白如果字符串长度不同，我的算法是无法工作的。

对于这种情况，我不知道该怎么办。

我在这里找到了一个很好的解决方案，但它也不起作用：

def anagrams(s1,s2):
    return [False, True][sum([ord(x) for x in s1]) == sum([ord(x) for x in s2])]

如果我运行这个函数并对两个字符串进行测试，我将获得如下输出：

Examples:

First Word: apple
Second Word: pleap

output: True

First Word: Moon starter
Second Word: Astronomer

output: False //however it should should be True because this words are anagrams 

- Daniel Chepenko

---

我的意思是它返回了False，但实际上应该是True。 - Daniel Chepenko

如果在去除空格等后，两个字符串的长度不同，则它们不是彼此的字谜。特别地，“astronomer”不是“moon starter”的字谜（显然：第二个字符串中有比第一个更多的“t”字符）。 - user5920214

@MagnusBuvarp 你不能使用集合来实现这个目的，因为集合不考虑每个字符出现的次数。 - miindlek

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Magnus Buvarp

@MagnusBuvarp 不行。例如，"aabc"和"abcc"在这种情况下会被视为真，这是错误的。 - miindlek

Answer 1

你的算法是正确的。你的问题在于没有考虑大小写字母。更改这两行代码即可：

alist1 = list(deleteSpaces(s1))
alist2 = list(deleteSpaces(s2))

为了

alist1 = list(deleteSpaces(s1).lower())
alist2 = list(deleteSpaces(s2).lower())

这将解决你的问题。作为替代，你可以简单地使用以下函数：

def anagrams(s1, s2):
    def sort(s):
        return sorted(s.replace(" ", "").lower())
    return sort(s1) == sort(s2)

如果您希望获得时间复杂度为O(n)的更快解决方案，应该使用计数器而不是对两个词进行排序:

from collections import Counter

def anagrams(s1, s2):
    def get_counter(s):
        return Counter(s.replace(" ", "").lower())

    return get_counter(s1) == get_counter(s2)

- miindlek

Answer 2

正如其他人指出的那样，你的算法给出了'false'结果，因为Moon starter和Astronomer实际上不是字谜。

你可以通过简单地使用可用的对象方法来大大改进你的算法。它们已经提供了所有的功能。

def normalize_str(s):
  return s.replace(" ","").lower()

def anagramSolution2(s1,s2):
  return sorted(normalize_str(s1)) == sorted(normalize_str(s2))

normalize_str 类似于你的 deleteSpaces，但它还会将所有内容转换为小写。这样，Moon 和 moon 将被视为相等。最终，您可能希望进行更严格或更松散的规范化，这只是一个示例。

调用 sorted 已经为您提供了一个 list，您不必进行显式转换。此外，通过 == 进行 list 比较会更有效地逐个比较 list 中的元素（这正是您使用 for 循环所做的），但更加高效。

- MisterMiyagi

Answer 3

类似这样的吗？

$ cat /tmp/tmp1.py
#!/usr/bin/env python

def anagram (first, second):
    return sorted(first.lower()) == sorted(second.lower())

if __name__ == "__main__":
    for first, second in [("abcd  rsh", "abcd x rsh"), ("123 456 789", "918273645  ")]:
        print("is anagram('{0}', '{1}')? {2}".format(first, second, anagram(first, second)))

它的意思是：

$ python3 /tmp/tmp1.py
is anagram('abcd  rsh', 'abcd x rsh')? False
is anagram('123 456 789', '918273645  ')? True

- boardrider

Answer 4

虽然有点懒，但是非常简洁的方法：

def anagram(a,b):
     return cleanString(a) == cleanString(b)

def cleanString(string):
    return ''.join(sorted(string)).lower().split()

- user8459437

Answer 5

def anagram(str1,str2):
    l1=list(str1)
    l2=list(str2)
    if sorted(l1) == sorted(l2):
        print("yess")
    else:
        print("noo")
str1='listen'
str2='silent'
anagram(str1,str2)

虽然不是最优化的解决方案，但运行良好。

- ravi tanwar

Answer 6

我发现这是最好的方法：

from collections import Counter

def is_anagram(string1, string2):
    return Counter(string1) == Counter(string2)

- Helton Wernik

Answer 7

a=input("string1:");
b=input("string2:");

def anagram(a,b):

    arra=split(a)
    arrb=split(b)
    arra.sort()
    arrb.sort()

    if (len(arra)==len(arrb)):

            if(arra==arrb):
                print ("True")
            else:
                ana=0;
                print ("False");

    else:
        print ("False");



def split(x):
    x=x.replace(' ','').lower()
    temp=[]
    for i in x:
        temp.append(i)
    return temp;


anagram(a,b)

- Joish

Answer 8

我尝试了这个，它有效了

def is_anagram(word1,word2):
        a = len(word1)
        b = len(word2)
        if a == b:
            for l in word1:
                if l in word2:
                    return True
        return False

- Samueltommzy