时间戳

首页 > 解决方案 > Scatter palindrome - 如何通过字典解析以找出形成回文的子串组合

python - Scatter palindrome - 如何通过字典解析以找出形成回文的子串组合

问题描述

我在一次面试中遇到了这个 HC 问题。我能够想出我称之为蛮力方法的方法。这是问题陈述：

查找给定字符串“aabb”中的所有分散回文。子串可以分散但重新排列以形成回文。示例：a、aa、aab、aabb、a、abb、b、bb、bba 和 b 是满足此条件的子字符串。

我的逻辑：

divide the str into substrings
counter = 0
if the len(substr) is even:
  and substr == reverse(substr)
  increment counter
else:
  store all the number of occurrences of each str of substr in a dict
  process dict somehow to figure out if it can be arranged into a palindrome
  ###### this is where I ran out of ideas ######

我的代码：

class Solution:
def countSubstrings(self, s: str) -> int:
    n = len(s)
    c=0
    for i in range(0,n-1): #i=0
        print('i:',i)
        for j in range(i+1,n+1): #j=1
            print('j',j)
            temp = s[i:j]
            if len(temp) == 1:
                c+=1
            # if the len of substring is even,
            # check if the reverse of the string is same as the string
            elif(len(temp)%2 == 0):
                if (temp == temp[::-1]):
                    c+=1
                    print("c",c)
            else:
                # create a dict to check how many times
                # each value has occurred
                d = {}
                for l in range(len(temp)):
                    if temp[l] in d:
                        d[temp[l]] = d[temp[l]]+1
                    else:
                        d[temp[l]] = 1
                print(d)

    return c


op = Solution()
op.countSubstrings('aabb')

到现在为止，很明显我是一个初学者。我确信有更好、更复杂的方法来解决这个问题。我的一些代码在这里改编自 visleck 的逻辑，我无法遵循它的后半部分。如果有人可以解释它，那也很棒。

标签： pythonalgorithmdata-structuresdynamic-programmingpalindrome

解决方案

作为部分答案，测试一个字符串是否为分散回文很简单：如果出现奇数次的字母数量最多为 1，则它是一个分散回文。否则不是。

它可以这样实现：

from collections import Counter

def scattered_palindrome(s):
    counts = Counter(s)
    return len([count for count in counts.values() if count % 2 == 1]) <= 1

例如，

>>> scattered_palindrome('abb')
True
>>> scattered_palindrome('abbb')
False

请注意，在任何阶段都没有必要将字符串与其反向进行比较。另外，请注意，我使用了Counter对象来跟踪字母计数。这是一种创建类似字典的字母计数集合的简化方法。

推荐阅读