[每日一題]131. Palindrome Partitioning

2021-02-21 每日一道算法題

題目難度：Medium

做題日期：2017年3月21日

提交地址：https://leetcode.com/problems/palindrome-partitioning/#/description

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

[  ["aa","b"],  ["a","a","b"]]

題目要求將一個字符串分成回文的組合，需要求出所有的符合要求的組合。比如字符串 aab 有兩種組合: aa, b 和 a, a, b。其中  aa, b, a 都是回文。

可以將問題分解成兩個子問題：如何分割字符串 和 判斷子串是否為回文。

判斷回文的方法

先說說簡單的問題：判斷回文的方法。

判斷回文有三種方法：雙指針、遞歸 和 Reverse 字符串。 

雙指針是通過兩個指針，分別指向字符串的首尾，如果當前的兩個字符相等則繼續，直到兩個指針相遇（或者位置相差 1）。

def is_palindrome(s)

    i, j = 0, s.length - 1

    while i < j do

        return false if s[i] != s[j]

        i += 1

        j += 1

    end

    return true

end


遞歸的思路跟雙指正類似：當前字符串是否為回文取決於首尾兩個字符是否相等 和 除去首尾兩個字符的子串是否為回文。

def is_palindrome(s)

    return true if s.length == 0 || s.length == 1

    s[0] == s[-1] && is_palindrome(s[1..-2])

end

Reverse 字符串的思路就是字符串反轉後判斷是否與原串相等，一般動態語言的字符串都有反轉字符串的API，所以代碼最簡單。

def is_palindrome(s)

    s == s.reverse 

end

如何分割字符串

分割字符串比較簡單，可以用兩種方式分割：其一，將字符串 AB 分割成 A + B連個字符串，會產生新的字符串，比如 abc 可以分割成 a + bc, ab + c, a + b + c；其二，用一個下標表示字符串的分割位置，這種方式沒有實際的分割字符串，只是用了一個標識位。

解決了上面的兩個問題，我們就可以做這道題了。

暴力回溯的思路比較簡單，如上面的分析所說，我們只需要窮舉字符串的所有子串的可能組合，去掉那些不符合要求的組合就可以了。

在窮舉所有的組合的時候，如果遇到當前分割的子串不是回文，則直接回溯。

非常感謝 五群的 @流風Susie 提供了如下的分析圖。


回溯算法最難理解的是回溯後，一定要把路徑中的上一個結果移除。

時間複雜度分析：

實例代碼

遞歸的思路跟暴力搜索有些許不同：將字符串分成 A + B兩個部分，如果 A 是回文，我們只需要求出 B 的所有回文的組合就行，然後將 A 和 B 結果做笛卡爾乘積就行了。 

比如求 aaab 的所有回文組合：

將字符串分割成 a + aab， a 子串是回文， aab子串的回文組合是 [a, a, b], [aa, b]， 所以合併組合: [a, a, a, b], [a, aa, b]

將字符串分割成 aa + ab,  aa 子串是回文， ab 子串的回文組合是 [a, b]， 所以合併組合: [aa, a, b]
... ...

遞推公式:

dp(j, i) = s[i] == s[j] && dp(j+1, i-1)

dp(j,i) 表示下標 j 到 下標 i 的子串是否是回文

長按下面的二維碼，關注每日一道算法題公眾號，跟我們一起學習算法！

群規

《每日一題算法群》群規

代碼規範

[每日一題]代碼規範v1.0

二分法相關的題目

[每日一題]二分法的三個區間控制套路

[每日一題]162. Find Peak Element

[每日一題]410. Split Array Largest Sum

[每日一題]209. Minimum Size Subarray Sum

[每日一題]240. Search a 2D Matrix II

[每日一題]74. Search a 2D Matrix

[每日一題]154. Find Minimum in Rotated Sorted Array II

[每日一題]174. Dungeon Game

數學相關的題目

[每日一題]264. Ugly Number II

[每日一題]202. Happy Number

[每日一題]172. Factorial Trailing Zeroes

[每日一題]483. Smallest Good Base

[每日一題]172. Factorial Trailing Zeroes

堆和棧

[周總結] stack 和 heap

[每日一題]402. Remove K Digits

[每日一題] 224. Basic Calculator

[每日一題]373. Find K Pairs with Smallest Sums

[每日一題]451. Sort Characters By Frequency

分治算法

[每日一題]分治算法(Divid and Conquer)總結

資源共享

[資源分享]分享一套清爽的Bootstrap UI 套件

[資源分享]Python算法進階之路

其他

面試心得

如何有效的區分小公司和創業公司

如何持續不斷的成長?


相關焦點

  • leetcode刷題指南之PalindromePairs
    算法的正確性：方法一無需舉例。對於方法二，如words = ["bat", "tab", "cat"]， 則map["tab"] = 0, map["bat"] = 1, map["tac"] = 2, 對於"bat", 我們發現map["bat"] = 1，且末尾串""為回文串。
  • 網際網路大廠算法面試題集合,看完我跪了!
    來源：https://github.com/azl397985856/leetcode介紹leetcode 題解
  • Leetcode題解 PalindromePairs
    則(0, 1)為一解；對於"bat", 我們發現map["tab"] = 0，且末尾串""為回文串。則(1, 0)為一解。故答案為[[0, 1], [1, 0]]。解法一class Solution {public:    bool judge(string& a, string& b){        int i = 0, j = b.size()-1;        while(i < a.size()&&
  • 一題一解(36)- How many pairs of 4-digit palindromes?
    一題：A palindrome is a positive integer whose digits are the same when
  • [每日一題]140. Word Break II
    群規《每日一題算法群》群規代碼規範[每日一題]代碼規範v1.0回溯相關[每日一題]131.Palindrome Partitioning[每日一題]139. Word Break[每日一題]357. Count Numbers with Unique Digits[每日一題]78. Subsets[每日一題]79.
  • 高三每日一題(133)
    高三每日一題（132）： 向量幾何運算是關鍵，一道三角形邊長組合最大值問題高三每日一題（131）： 分離變量，一道任意與存在求參的小題高三每日一題（130）：構造三角形高，解雙曲線離心率取值範圍>高三每日一題（57）：挖掘內涵，直線與圓高三每日一題（56）：構建幾何，二元最值高三每日一題（55）：緊給目標，均值換元導數一題高三每日一題（54）：另解網上熱議的一道題恆成立問題
  • [每日一題]78. Subsets
    上一道題（ [每日一題]131. Palindrome Partitioning ）回文分割字符串的難度應該大於今天的題。排列組合題，有比較多的變種，比如給定一個字符串，求其全排列等。因為需要窮舉所有的方案，所以一般思路都是暴力搜索。
  • leetcode刷題指南之shortestPalindrome
    3string shortestPalindrome(string s) { 4    reverse (s.begin (), s.end ()); 5    string h = s;  6    reverse (h.begin (), h.end ()); 7    unsigned long long hash1 = 0, hash2 = 0, seed = 131
  • 【每日一題】(287)障壁島
    格陵蘭島的冰山【每日一題】（192）衝越扇【每日一題】（193）高山出好茶【每日一題】（194）綠色圓形農田【每日一題】（195）珊瑚礁形態與風向關係【每日一題】>【每日一題】（226）「地冰花」【每日一題】（227）阿特拉斯山【每日一題】（228）油橄欖【每日一題】（229）雪花形態【每日一題】（230）「地穿甲現象」
  • 【每日一題】(245)馬拉開波湖
    ）特殊的瀑布【每日一題】（190）湧潮【每日一題】（191）格陵蘭島的冰山【每日一題】（192）衝越扇【每日一題】（193）高山出好茶【每日一題】（194）綠色圓形農田【每日一題】（195）珊瑚礁形態與風向關係【每日一題】（196）植物牆【每日一題】（197）棄風限電1【每日一題】（198）棄風限電2【每日一題】（199）棄風限電
  • 【每日一題】(869)比溼
    ——別讓未來的你，討厭現在的自己（溫馨提醒：由於微信改版，打亂了發布時間，為了保證大家可以及時看見老師的推送，可將本公眾號設為星標就可以第一時間看到推送哦）精選好題訓練思維據此完成12～13題。大家都在關注（超連結，可以查看早期全部內容）【每日一題】全部習題（862道）搜尋引擎【每日一題】《自然地理》分類整理搜尋引擎【每日一題】《人文地理》分類整理搜尋引擎【每日一題】《中國地理》分類整理搜尋引擎【每日一題】《世界地理》分類整理搜尋引擎
  • 【每日一題】(907)蘭嶼島
    （溫馨提醒：由於微信改版，打亂了發布時間，為了保證大家可以及時看見老師的推送，可將本公眾號設為星標就可以第一時間看到推送哦）精選好題訓練思維15. 蘭嶼紅頭山熱帶季雨林，發育於山的西南面，主要是因為（ ）A.
  • 《龍族幻想》12月22日每日一題答案是什麼 每日一題答案分享
    導 讀 最近玩龍族幻想的玩家都在問，遊戲裡面每日一題答案是什麼了，今天的問題是誰降臨幻境之海，在平行世界掀起軒然大波
  • 再見, 數學分析每日一題
    曾無數次地想這天快點來到, 因為每日的堅持確實太累. 今天它真來了, 卻帶來的是些許傷感. 想到 2021 考研的路程才剛剛過半, 之後還有半年的時間陪伴大家一起進行強化衝刺, 內心也是充滿了期待. 每日一題的結束只是代表課本的學習該結束了, 而真正的考研廝殺才剛剛開始, 所以親愛的你們不能有絲毫的懈怠, 接下來該你們閃亮登場了!120 天, 揚哥經歷了很多.
  • 《三國殺》1月5日每日一題答案是什麼 每日一題答案分享
    導 讀 三國殺1月5日每日一題問題 下列武將中，沒有改版新武將的是哪位？
  • 《拳皇98OL》11月26日每日一題答案是什麼 每日一題答案一覽
    導 讀 拳皇98ol和許多騰訊遊戲一樣，都有每日一題的活動。
  • 【重磅】影像科每日一題精選(十六)
    （全文共計1303字，預計閱讀時間為4分鐘）導讀：職稱考試報名後，在我們科，我給科室人員安排了每日一題，來幫助他們通過職稱考試，下面我把我們最近六天發布的題也分享給大家。往期回顧：【重磅】影像科每日一題精選（一）【重磅】影像科每日一題精選（二）【重磅】影像科每日一題精選（三）【重磅】影像科每日一題精選（四）【重磅】影像科每日一題精選（五）【重磅】影像科每日一題精選（六）【重磅】影像科每日一題精選（七）【重磅】
  • 【每日一題】(225)南非的「桌山」
    【每日一題】（188）亞馬爾半島馴鹿【每日一題】（189）特殊的瀑布【每日一題】（190）湧潮【每日一題】（191）格陵蘭島的冰山【每日一題】（192）衝越扇【每日一題】（193）高山出好茶【每日一題】（194）綠色圓形農田【每日一題】（195）珊瑚礁形態與風向關係【每日一題】（196）植物牆【每日一題】（197）棄風限電
  • 必勝課英語每日一題1114
    G7必勝課英語每日一題1114Her cousin is        years old and it is her (