制作字谜：临时字谜长度减法

Question

问题：给定两个长度可能相同或不同的字符串，确定使它们成为变位词所需的最少字符删除数。可以从任一字符串中删除任何字符。

我的方法：

def anagramlength(string1,string2):
    temp = []
    if len(string1)> len(string2):
        x= string2
        y=string1
    else:
        x = string1
        y=string2
    for c in x:
        if c in y:
            temp.append(c)
        else:
            continue
    return (len(x)- len(temp)) + len(y)- len(temp)

使用测试用例：

anagramlength('bugexikjevtubidpulaelsbcqlupwetzyzdvjphn','la‌joipfecfinxjspxmevqx‌uqyalhrsxcvgsdxxkacs‌pbchrbvvwnvsdtsrdk')

我得到 28，而正确答案是 40。你能帮我看看我的程序哪里出了问题吗？

Answer 1

通过使用字典来存储每个字符串的字母，您的算法可以减少到线性时间。

def anagramlength(string1,string2):
    difference = {}


    for letter in string1:
        if letter not in difference:
            difference[letter] = 0
        difference[letter] += 1

    for letter in string2:
        if letter not in difference:
            difference[letter] = 0
        difference[letter] -= 1

    return sum(abs(n) for n in difference.values())

Answer 2

更正代码：

def anagramlength(string1,string2):
    temp = []
    if len(string1)> len(string2):
        x= string2
        y=string1
    else:
        x = string1
        y=string2
    lenb=len(y)
    for c in x:
        if c in y:
            temp.append(c)
            y = list(y)
            y[y.index(c)]= None
    return (len(x)- len(temp)) + lenb - len(temp)

Answer 3

这可以通过使用字典来存储字符来简化。

def anagramlength(str1,str2):
    dict = {}


    for char in str1:
        if char not in dict:
            dict[char] = 0
        dict[char] += 1

    for char in str2:
        if char not in dict:
            dict[char] = 0
        dict[char] -= 1

return sum(abs(n) for n in dict.values())

Answer 4

这是另一个不使用字典的简化解决方案：

a = input().strip()
b = input().strip()

def number_needed(a, b):
    n=0
    for i in a:
        if i not in b or a.count(i)> b.count(i):
            n += 1
            a=a.replace(i, '', 1)
    for j in b:
        if j not in a or b.count(j) > a.count(j):
            n +=1
            b=b.replace(j, '', 1)
    return n

print(number_needed(a, b))

制作字谜：临时字谜长度减法

Making Anagrams : Temp Anagram length subtraction method

python

anagram