【leetcode】1147. Longest Chunked Palindrome Decomposition

题目如下：

Return the largest possible k such that there exists a_1, a_2, ..., a_k such that:

Each a_i is a non-empty string;

Their concatenation a_1 + a_2 + ... + a_kis equal to text;

For all 1 <= i <= k, a_i = a_{k+1 - i}.

Example 1:
Input: text = "ghiabcdefhelloadamhelloabcdefghi"

Output: 7

Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".
Example 2:
Input: text = "merchant"

Output: 1

Explanation: We can split the string on "(merchant)".
Example 3:
Input: text = "antaprezatepzapreanta"

Output: 11

Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".
Example 4:
Input: text = "aaa"

Output: 3

Explanation: We can split the string on "(a)(a)(a)".
Constraints:

text consists only of lowercase English characters.

1 <= text.length <= 1000

解题思路：本题不算太难，我的方法是贪心算法+双指针。首先引入head和tail两个变量，分别等于text[0]和text[-1]。如果head等于tail，表示这两者可以组成回文段的两部分，再令head等于text[1]，tail等于text[-2]；如果两者不相等，令head = head + text[0]，tail = text[-2] + tail，直到head 等于tail为止。原则就是每遇到head等于tail的情况，表示这两段是回文段的一部分，重置head 和tail的值。

代码如下：

class Solution(object):

    def longestDecomposition(self, text):

        """

        :type text: str

        :rtype: int

        """

        res = 0

        head_inx = 0

        tail_inx = len(text) - 1

        head = ''

        tail = ''

        while head_inx <= tail_inx and head_inx < len(text) and tail_inx >= 0:

            if head == '' and tail == '':

                head = text[head_inx]

                tail = text[tail_inx]

                head_inx += 1

                tail_inx -= 1

            elif head == tail:

                res += 2

                head = text[head_inx]

                tail = text[tail_inx]

                head_inx += 1

                tail_inx -= 1

            else:

                #head_inx += 1

                #tail_inx -= 1

                head = head + text[head_inx]

                tail = text[tail_inx] + tail

                head_inx += 1

                tail_inx -= 1

        res += 2 if  head == tail and head_inx - len(head) != tail_inx + len(tail) else 1

        return res if res != 0 else 1

巴特西

【leetcode】1147. Longest Chunked Palindrome Decomposition

最新文章

热门文章