LintCode(136): Palindrome Partitioning

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

Return all possible palindrome partitioning of s.

Have you met this question in a real interview? 

Yes

Example

given s = "aab",
Return

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

回溯法，这种求combination的题目，一般就是DFS 的暴力搜索了，连模板其实都一样。。。之前做OA的时候碰到过一个求按照棋盘走的电话号码搜索，都是思想一样的。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

class Solution { public: /** * @param s: A string * @return: A list of lists of string */ vector<vector<string>> partition(string s) { // write your code here vector<vector<string>> result; vector<string> solution; if (s.empty()) return result; helper(result, solution, s, 0); return result; } void helper(vector<vector<string>>& result, vector<string>& solution, const string& s, int ind) { if (ind>=s.size()){ result.push_back(solution); return; } for (int i=ind; i<s.size(); i++){ if (!isPalindrome(s, ind, i)) continue; solution.push_back(s.substr(ind, i-ind+1)); helper(result, solution, s, i+1); solution.pop_back(); } } bool isPalindrome(const string& s, int beg, int end){ while(beg<end){ if (s[beg++]!=s[end--]) return false; } return true; } };