比较两个不同字符串以匹配的排列

Question

我正在绞尽脑汁解决这个问题。

我正在尝试比较两个字符串，例如：

a = 'apple'
b = 'ppale'

如果我使用排列法，可以重新生成变量b，它可以匹配变量a。

我写了代码，天知道为什么，我只得到 False 值，即使我期望 True。

import itertools

def gen(char, phrase):
    char = list(char)

    wordsList = list(map(''.join, itertools.permutations(char)))
    for word in wordsList:
        if word == phrase:
            return True
        else:
            return False

print(gen('apple', 'appel')) # should be True
print(gen('apple', 'elppa')) # should be True
print(gen('apple', 'ap')) # should be False

Answer 1

问题是您在循环的第一次迭代时返回，无论是否存在匹配项。特别是，您在 第一次 时返回 False 不匹配。相反，您需要在返回 False:

之前完成整个循环

def gen(char, phrase):
    char = list(char)

    wordsList = list(map(''.join, itertools.permutations(char)))
    for word in wordsList:
        if word == phrase:
            return True
    return False

请注意，可以进行一些改进。一个是没有必要做 char = list(char)，因为 char 已经是一个可迭代的。此外，无需将地图结果扩展到列表中。它只是被用作可迭代对象，因此可以直接使用，这可能会节省大量内存：

def gen(char, phrase):
    wordsIter = map(''.join, itertools.permutations(char))
    for word in wordsIter:
        if word == phrase:
            return True
    return False

但是，由于您只是比较相同字符的两个单词，因此您实际上不需要生成所有排列。相反，您只需要检查两组字符是否相同（允许字符的多个实例，因此从技术上讲，您想要比较两个 multisets）。您可以更更有效地执行此操作，如下所示：

import collections

def gen(char, phrase):
    counter1 = collections.Counter(char)
    counter2 = collections.Counter(phrase)
    return counter1 == counter2

这是一个复杂度为 O(n) 的算法，这是解决此问题的最佳算法。这比生成排列快多。对于长字符串，它也比排序字母和比较排序结果快得多，这是 O(n*log(n)).

示例输出：

>>> gen("apple", "elxpa")
False
>>> gen("apple", "elppa")
True
>>> gen("apple", "elpa")
False
>>>

注意这只returns True如果字母相同，每个字母的个数相同

如果你想加快两个字符串长度不同的情况，你可以在计算字符数之前添加一个快速检查 returns False 如果长度不同。

Answer 2

它不起作用的主要原因是，一旦出现第一个不匹配，您的循环就会 returning False 返回给调用者。你想要的是这样的：

for word in wordsList:
    if word == phrase:
        return True
return False

这将测试一个或多个排列；如果一个匹配，它会立即 return True，但只有在它们都匹配不上后，它才会 return False.

此外，char = list(char) 也没有必要。字符串是可迭代的，就像 list，因此您可以将它用作 permutations().

的参数

Answer 3

您可以使用的另一种方法是循环遍历一个单词的字母，如果存在另一个单词，则删除该单词中的字母。如果第一个词迭代后，第二个词为空，则为变位词：

def anagram(word1, word2):
  for letter in word1:
    word2 = word2.replace(letter,"",1)
  if word2 == "":
    return True
  return False

a = "apple"
b = "pleap"

print(anagram(a,b)) #returns True

a = "apple"
b = "plaap"

print(anagram(a,b)) #returns False

Answer 4

您可以更简单地做到这一点：对每个单词中的字母进行排序并比较是否相等。

def gen(a, b):
    return sorted(a) == sorted(b)

比较两个不同字符串以匹配的排列

Permutations to compare two different string to match

python

permutation

itertools