Palindrome Partitioning

 

Total Accepted: 21056 

Total Submissions: 81036

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"]  ]

题意：切割字符串，使每一个子串都是回文

思路：dfs

选择一个切割点时，假设从起点到切割点的子串是回文，那么该切割点是合法的。能够选择

按这个规则dfs枚举就能够了

复杂度：时间O(n)。空间O(log n)

vector
     
      
        >res;bool is_palindrome(const string &s, int start, int end){	while(start < end){		if(s[start] != s[end - 1]) return false;		++start; --end;	}	return true;}void dfs(const string &s, int cur, vector
       
        & partitions){	int size = s.size();	if(cur == size){		res.push_back(partitions);	}	for(int end = cur + 1; end <= size; ++end){		if(is_palindrome(s, cur, end)){			partitions.push_back(s.substr(cur, end - cur));			dfs(s, end, partitions);			partitions.pop_back();		}	}}vector
        
         
          > partition(string s) {	vector
          
            tem; dfs(s, 0, tem); return res;}