131. 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.For example, given s = "aab",Return[  ["aa","b"],  ["a","a","b"]]

解析

• The Idea is simple: loop through the string, check if substr(0, i) is palindrome. If it is, recursively call dfs() on the rest of sub string: substr(i+1, length). keep the current palindrome partition so far in the ‘path’ argument of dfs(). When reaching the end of string, add current partition in the result.

• 理解dfs的递归思想，经典！！

• 控制输出的顺序：牛客网的oj系统不合理，但是也值得思考！简单的reverse(ret.begin(), ret.end());逆序输出不对的。

对应输出应该为:

[["d","d","e"],["dd","e"]]

你的输出为:

[["dd","e"],["d","d","e"]]

```

// Palindrome(回文) Partitioningclass Solution_131_ref {    // date 2017/12/29 11:14    // 如果要求输出所有可能的解，往往都是要用深度优先搜索。如果是要求找出最优的解，或者解的数量，往往可以使用动态规划    // Reference：https://leetcode.com/problems/palindrome-partitioning/discuss/41964public:    vector
    
     
      > partition(string s) {        vector
      
       
         > ret;        if (s.empty()) return ret;        vector
        
          path;        dfs(0, s, path, ret);        return ret;    }    void dfs(int index, string& s, vector
         
          & path, vector
          
           
             >& ret) { if (index == s.size()) { ret.push_back(path); return; } for (int i = index; i < s.size(); ++i) { //先以步长为1找回文串，找到了下一个回文串也是以步长为1开始 ；下一轮循环以步长为2开始，这样保证所有子回文串找到 if (isPalindrome(s, index, i)) { path.push_back(s.substr(index, i - index + 1)); dfs(i + 1, s, path, ret); path.pop_back(); } } } bool isPalindrome(const string& s, int start, int end) { while (start <= end) { if (s[start++] != s[end--]) return false; } return true; }};class Solution_131{public: bool ispalindrome(string str) { if (str.size()==1) { return true; } bool flag = true; for (int i = 0; i < str.size()/2; i++) { if (str[i]==str[str.size()-1-i]) { continue; } else { flag = false; } } return flag; } bool isPalindrome1(string s){ return s == string(s.rbegin(), s.rend()); } void dfs(string src, vector
            
              &path, vector
             
              
               > &ret){ if (src.size() <= 0 ) { return; //递归退出条件 } if (ispalindrome(src)) //最后部分的子串为回文串，结束此处递归 // { path.push_back(src); ret.push_back(path); path.pop_back(); } string temp; for (int j = 1; j < src.size();j++) //限制了长度2以上； { temp = src.substr(0, j); if (ispalindrome(temp)) { path.push_back(temp); dfs(src.substr(j),path,ret); //ret.push_back(path); path.pop_back();// } } return; } void dfs1(string s, vector
               
                 &cur, vector
                
                 
                  > &res){ if (s == ""){ res.push_back(cur); return; } for (int i = 1; i <= s.length(); ++i) { string sub = s.substr(0, i); if (ispalindrome(sub)){ cur.push_back(sub); dfs1(s.substr(i, s.length() - i), cur, res); cur.pop_back(); } } } vector
                  
                   
                    > partition(string s) { vector
                    
                     
                      > ret; vector
                      
                        path; dfs1(s, path, ret); //深度递归 return ret; }};
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

题目来源