回文分区

Question

给定一个字符串，将其拆分为尽可能少的字符串，使每个字符串都是回文

k = "racecarannakayak"

palin = [] # to get palindrome strs  

i, j = 0, 2

while j != len(k) + 1:
    if k[i:j] == k[:j][::-1]:
        palin.append(k[i:j])
        i += 1

    j += 1


print(palin)

结果是["racecar"]，但应该是["racecar", "anna", "kayak"]

我的代码有什么问题

Answer 1

您的代码存在一些问题

• 首先，您的指针i保持迭代，即使您的点j是 在大多数迭代中都比它小。意思是你在做什么 像k[10:2]这样的东西毫无意义
• 其次，指针j只在整个数组上工作一次。意思 您需要多次传递，或者需要将i指针重置为 如果找到回文，则j指针的最后位置
• 第三，没有条件确保单个字母字符串 你的倒装逻辑不认为是回文
• 最后，正如@fas在评论中提到的，似乎有一个拼写错误k[i:j]==k[i:j][::-1]而不是你写的

如果你考虑以上3点并做出必要的改变，你应该对你的代码得到正确的结果如下：

k = "racecarannakayak"

palin = [] # to get palindrome strs  

i, j = 0, 2

while j != len(k) + 1:
    if k[i:j] == k[i:j][::-1] and len(k[i:j])>2:  #Check length is >2
        palin.append(k[i:j])
        i=j             #Reset i pointer to current j
    j += 1


print(palin)

['racecar', 'anna', 'kayak']