回文分区

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']

回文分区

Palindrome Partitions

python

algorithm

partitioning

python-3.x