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

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

但是，由于您只是比较相同字符的两个单词，因此您实际上不需要生成

所有

排列。相反，您只需要检查两组字符是否相同（允许字符的多个实例，因此从技术上讲，您需要比较两个多重集）。您可以按照以下方式更有效地完成此操作：

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

请注意，仅当字母相同且每个字母的数量相同时才返回

True

。

如果您想加快两个字符串长度不同的情况，您可以在计算字符之前添加一个快速检查，如果长度不同，则返回 

False

。

它不起作用的主要原因是，一旦发生第一个不匹配，您的循环就会返回

False

回到调用者。你想要的是这样的：

Answer 2

将测试一种或多种排列；如果有一个匹配，它会立即返回

True

，但只有当全部匹配失败后才会返回

False

。

此外，无需执行

char = list(char)

。字符串是可迭代的，就像

list

一样，因此您可以将其用作

permutations()

的参数。

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

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

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 string_permute(first_str: str, second_str: str) -> bool:
    cache = {}
    for ch in first_str:
        cache[ch] = cache.get(ch, 0) + 1
    for ch in second_str:
        cache[ch] = cache.get(ch, 0) - 1
    for ch in cache:
        if cache[ch] != 0:
            return False
    return True

O(n) 时间复杂度和 O(n) 空间复杂度

Answer 5