如何找出字符串的两个相等部分是否是 python 中的字谜

Question

我正在尝试编写执行以下操作的代码：

将多个字符串作为输入
将每个字符串拆分为两个等长的连续子字符串
Returns 为使两个子串互相变位而改变的最少字符数（如果不可能，则必须 return -1）。

样本输入

6
aaabbb
ab
abc
mnop
xyyx
xaxbbbxx

示例输出

有关问题的更详细说明，请查看this link（无需登录或注册）。

我已经很好地解决了这个问题，但似乎我没有得到正确的结果，我的输出通常比预期的要大或小一点，我真的不知道是什么导致了这个问题.这是我的代码：

n = int(input())
user_input = []

for k in range(n):
    user_input.append(input())

results = []

for i in user_input:
    if len(list(i))%2 == 0:
        left = i[:len(list(i))//2]
        right = i[len(list(i))//2:]

        left_dict = dict((letter,left.count(letter)) for letter in set(left))
        right_dict = dict((letter,right.count(letter)) for letter in set(right))

        if left_dict == right_dict:
            results.append(0)

        else:
            shared_items = {k: left_dict[k] for k in left_dict if k in right_dict and left_dict[k] == right_dict[k]}
            
            results.append(len(left) - len(shared_items))
            

    else:
        results.append(-1)

print(results)

感谢提前提供的任何帮助。

Answer 1

如果相同的字母以相同的出现次数出现，则两个词是变位词。

from collections import Counter

sl = ["aaabbb", "ab", "abc", "mnop", "xyyx", "xaxbbbxx"]


def f(s):
    if len(s)%2 != 0:
        return -1

    a = s[:len(s)//2]
    b = s[len(s)//2:]

    print(Counter(b) - Counter(a))
    return sum( (Counter(b) - Counter(a)).values() )

list(map(f, sl))

Counter({'b': 3})
Counter({'b': 1})
Counter({'o': 1, 'p': 1})
Counter()
Counter({'b': 1})

[3, 1, -1, 2, 0, 1]

Answer 2

你开始很好，计算了两个子字符串中每个字符的计数，但你从未在技术上使用过这种能力。

在此声明中：

shared_items = {k: left_dict[k] for k in left_dict if k in right_dict and left_dict[k] == right_dict[k]}

您只需计算同时在字典中且具有相同计数的项目：

例如。在你的第 6 个测试用例中：

xaxbbbxx

left_dict 将是 {'b': 1, 'a': 1, 'x': 2}
right_dict 将是 {'b': 2, 'x': 2}

和shared_item你的计算方式会给你：{'x':2}

但这并没有正确列出所有共享的项目。

正确的号码。 shared_items 的应该是：{'x':2, 'b':1}

因此，
然后我们可以做的是计算 left_dict 和 right_dict.
中常见的项目数量的最小值即 min(left_dict[k],right_dict[k])

result.append语句也会相应改变：

    else:
        shared_items = {k:min(left_dict[k],right_dict[k]) for k in left_dict if k in right_dict}
        
        results.append(len(left)-sum(shared_items.values()))

完全执行：

n = int(input())
user_input = []

for k in range(n):
    user_input.append(input())

results = []

for i in user_input:
    if len(list(i))%2 == 0:
        left = i[:len(list(i))//2]
        right = i[len(list(i))//2:]

        left_dict = dict((letter,left.count(letter)) for letter in set(left))
        right_dict = dict((letter,right.count(letter)) for letter in set(right))
        if left_dict == right_dict:
            results.append(0)

        else:
            shared_items = {k:min(left_dict[k],right_dict[k]) for k in left_dict if k in right_dict}
            
            results.append(len(left)-sum(shared_items.values()))
            

    else:
        results.append(-1)

print(results)

输入：

6
aaabbb
ab
abc
mnop
xyyx
xaxbbbxx

输出：

[3, 1, -1, 2, 0, 1]

然后您当然可以使用并打印 '\n'.join(results) 以获得所需格式的输出。

如何找出字符串的两个相等部分是否是 python 中的字谜

How to find out if the two equal parts of a string are anagrams in python

python

python-3.x

list

dictionary

anagram