iT邦幫忙

1

【小馬的LeetCode練功坊】1147. Longest Chunked Palindrome Decomposition- 字串分解成最多區塊成為迴文

參考題目: 1147. Longest Chunked Palindrome Decomposition
題意: 回傳字串最多的迴文分解個數。
例: text = "ghiabcdefhelloadamhelloabcdefghi"
可分解為 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)" 共七段
使用貪婪法。

思路如下:
https://ithelp.ithome.com.tw/upload/images/20200710/20117114j3X9UmGk6E.png
(參考資料: leetcode討論區- Easy Greedy with Prove)

想法想通了其實也不難,
如果有一個長的字串B1和短的字串R1都滿足前後相同的話(B1=B2, R1=R4),
那字串一定可以切割成更短的,
所以我們可以貪婪的從字串兩端搜索,
只要前後字串相同的話就算成功

證明: 若B1=B2, R1=R4,由於B1=B2,
強迫R1=R2=R3=R4,
因此把B1再切割成更短的三段也可以

程式碼:

class Solution:
    def longestDecomposition(self, S:str)-> int:
        res, leftIdx, rightIdx = 0, 0, len(S)-1
        left, right = "", ""
        for _ in range(len(S)):
            left, right= left + S[leftIdx], S[rightIdx] + right
            leftIdx, rightIdx = leftIdx+1, rightIdx-1
            if left == right:
                res, left, right = res + 1, "", ""
        return res

尚未有邦友留言

立即登入留言