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"] ]
將一個字符串,進行分段,每段都是一個回文。
列出所有的分法。
基本思路:
深度優先遞歸。
在剩余字符中,逐步償試,找一個回文子串;若找到,則刨掉此回文後,在剩余的子符繼續進行前面的操作。
若剩余字符為空,則找到一個組合。
判斷一個字串是否是回文,用頭尾兩個指針,向中間移動。
在leetcode上實際執行時間為12ms。
class Solution { public: vector> partition(string s) { vector > ans(1); dfs(ans, s, 0); ans.pop_back(); return ans; } void dfs(vector > &ans, const string &s, int start) { if (start == s.size()) { ans.push_back(ans.back()); return; } for (int i=start; i end; } };