检查需要删除多少个字符才能在 Python 中生成字谜

Question

我写了 python 代码来检查需要从两个字符串中删除多少个字符才能使它们成为彼此的变位词。

这是问题陈述“给定两个字符串 and ，这两个字符串的长度可能相同，也可能不相同，确定生成和变位词所需的最少字符删除数。可以从任一字符串中删除任何字符字符串

def makeAnagram(a, b):
    # Write your code here
    ac=0 # tocount the no of occurences of chracter in a
    bc=0    # tocount the no of occurences of chracter in b
    p=False     #used to store result of whether an element is in that string
    c=0        #count of characters to be deleted to make these two strings anagrams
    t=[]        # list of previously checked chracters
    
    for x in a:
        if x in t == True:
            continue
        ac=a.count(x)
        t.insert(0,x)
        for y in b:
            p = x in b
            if p==True:
                bc=b.count(x)
                if bc!=ac:
                    d=ac-bc
                    c=c+abs(d)

            elif p==False:
                c=c+1 
                               
    return(c)

Answer 1

您可以为此使用 collections.Counter：

from collections import Counter

def makeAnagram(a, b):
    return sum((Counter(a) - Counter(b) | Counter(b) - Counter(a)).values())

Counter(x)（其中 x 是一个字符串）returns 一个将字符映射到它们在字符串中出现的次数的字典。

Counter(a) - Counter(b) 给你一个字典，将 b 中过多的字符映射到它们在 b 中出现的次数多于它们在 [=17] 中出现的次数=].

Counter(b) - Counter(a) 和上面一样，但是对于 a.

中过多的字符

| 合并两个生成的计数器。然后我们取这个值，并将它们相加得到在任一字符串中过多的字符总数。这相当于构成一个字谜需要删除的最少字符数。

至于为什么你的代码不起作用，我无法确定其中的任何一个问题。为了获得下面的代码，我所做的只是一些简化（例如删除不必要的变量，将 a 和 b 一起循环，删除 == True 和 == False，将 t 替换为 set]，给变量起描述性的名称等），代码开始运行。这是简化的工作代码：

def makeAnagram(a, b):
    c = 0 # count of characters to be deleted to make these two strings anagrams
    seen = set() # set of previously checked characters
    for character in a + b:
        if character not in seen:
            seen.add(character)
            c += abs(a.count(character) - b.count(character))
    return c

我建议您着重学习如何编写 simple/short 代码。与实际处理算法并获得结果相比，这似乎并不重要。这看起来像是清理或造型工作。但它的回报是巨大的。错误更难在简单的代码中引入，但更容易发现。通常，简单的代码也比等效的复杂代码具有更高的性能，这要么是因为程序员能够更轻松地找到改进它的方法，要么是因为更简洁的代码自然而然地产生了更高性能的方法。

Answer 2

假设只有小写字母

想法是为每个字符的字符串和存储频率创建字符计数数组。现在迭代两个字符串的计数数组，两个字符串中任何字符的频率差异 abs(count1[str1[i]-‘a’] – count2[str2[i]-‘a’]) 是任一字符串中要删除的字符数。

CHARS = 26
 
# function to calculate minimum
# numbers of characters
# to be removed to make two
# strings anagram
def remAnagram(str1, str2):
 
    
    count1 = [0]*CHARS
    count2 = [0]*CHARS
 
    i = 0
    while i < len(str1):
        count1[ord(str1[i])-ord('a')] += 1
        i += 1
 
    i =0
    while i < len(str2):
        count2[ord(str2[i])-ord('a')] += 1
        i += 1
 
    # traverse count arrays to find
    # number of characters
    # to be removed
    result = 0
    for i in range(26):
        result += abs(count1[i] - count2[i])
    return result

这里的时间复杂度是O(n + m) 其中n和m是两个字符串的长度 Space 复杂度为 O(1)，因为我们只使用大小为 26

的数组

这可以通过仅使用单个数组进行计数来进一步优化。

在这种情况下，对于字符串 s1 -> 我们增加计数器对于字符串 s2 -> 我们递减计数器

def makeAnagram(a, b):
    buffer = [0] * 26
    for char in a:
        buffer[ord(char) - ord('a')] += 1
    for char in b:
        buffer[ord(char) - ord('a')] -= 1
    return sum(map(abs, buffer))

if __name__ == "__main__" :
 
    str1 = "bcadeh"
    str2 = "hea"
    print(makeAnagram(str1, str2))

输出：3

检查需要删除多少个字符才能在 Python 中生成字谜

Check how many character need to be deleted to make an anagram in Python

python

anagram