0131.md

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.

example:
given s = "aab",
Return

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

思路

回溯法，其实就是一个遍历的过程，对于二维数组中的每一个结果，每一单个string总是回文的，所以对于第一个string而言，它
的长度可能是1~s.sz-1.当第一个string是单个字符的时候，其中"一组"结果就是s[0]加上后面字符串可以产生的结果。如果第一
个string是两个字符的时候，即字符串长度为2的时候其中一组结果就是s.substr(0,2)加上后面字符串可以产生的结果···

如例子s="bcbevvfbcb":

第一个string是一个字符的时候可能的结果为(因为第一个string已经决定,后面又是一个相同的子问题):
["b","c","b","e","v","v","f","b","c","b"]

["b","c","b","e","v","v","f","bcb"]

["b","c","b","e","vv","f","b","c","b"]

["b","c","b","e","vv","f","bcb"]

第一个string使三个字符的时候可能结果为

["bcb","e","v","v","f","b","c","b"]

["bcb","e","v","v","f","bcb"]

["bcb","e","vv","f","b","c","b"]

["bcb","e","vv","f","bcb"]]

对于一个简单的例子 : s = "aab"
回溯的过程为：

"a"是回文，部分结果肯定为["a"]加上字符串"ab"的结果，递归处理"ab".
    
    第二个"a"也是回文，部分结果肯定为 ["a","a"]加上字符串"b"的结果，递归处理"b".
    
        "b"是回文，部分结果肯定为["a","a","b"]。即这是一个结果。不能继续向下递归，返回上层。
    
    "ab"不是回文，不做处理。不能继续向下递归，返回上层。
    
"aa"是回文，部分结果肯定为["aa"]加上字符串"b"的结果，递归处理"b"

    "b"是回文部分结果肯定为["aa","b"]。即这是结果之一，不能继续向下递归，返回上层。
    
"aab"不是回文，不能继续向下递归，当层是最外层结束循环。

代码

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int sz = s.size(); 
        vector<vector<string>> result;
        if(sz==0) return result;
        
        vector<string> sub_vec;
        dfs(s,result,0,sub_vec);
        return result;
    }
    
    void dfs(string &s,vector<vector<string>> &result,int begin_index,vector<string> &sub_vec){
        if(begin_index==s.size()){
            result.push_back(sub_vec);
            return ;
        }
        for(int i=begin_index;i<s.size();++i){
            if(is_palindrome(s,begin_index,i)){
                sub_vec.push_back(s.substr(begin_index,i-begin_index+1));
                dfs(s,result,i+1,sub_vec);
                sub_vec.pop_back();
            }
        }
    }
    
    bool is_palindrome(string& s,int left,int right){
        while(left<=right){
            if(s[left++]==s[right--]) continue;
            else return false;
        }
        return true;
    }
};

func partition(s string) [][]string {
	res := make([][]string, 0, 1)
	curList := make([]string, 0, len(s))
	backtrack(s, 0, len(s)-1, &res, curList)
	return res
}

func backtrack(s string, left, right int, res *[][]string, curList []string) {
	if left > right {
		subRes := make([]string, len(curList))
		copy(subRes, curList)
		*res = append(*res, subRes)
	}
	for i := left; i <= right; i++ {
		//fmt.Printf("s[left:i+1]: %+v\n", s[left:i+1])
		if !isPalindrome(s[left : i+1]) {
			continue
		}
		curList = append(curList, s[left:i+1])
		backtrack(s, i+1, right, res, curList)
		curList = curList[:len(curList)-1]
	}
}

func isPalindrome(s string) bool {
	for i, j := 0, len(s)-1; i <= j; i, j = i+1, j-1 {
		if s[i] != s[j] {
			return false
		}
	}
	return true
}