LeetCode -- Palindrome Partitioning

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


把字符串s進行分割，要求分割後的每個子串（s[i...j]，其中i,j∈[0,n)）都是回文。


本題算是回溯問題，與Combination Sum的1和2屬於同類問題。


使用經典的回溯模型：
BackTracking(start , current, result):
if start is end :
add current to result


i = start to end:
currentAdd(the [i]th element);
BackTracking(i+1, current, result)
currentRemove(the [i]th element)


至於判斷回文的過程就不介紹了，判斷兩頭字符是否相等，直到中間元素位置。




實現代碼：

public class Solution {
    public IList> Partition(string s) 
    {
        if(string.IsNullOrEmpty(s))
        {
    		return new List>();
    	}
    	
    	var result = new List>();
    	Travel(s, 0, new List() , ref result);
    	
    	return result;
    }
	


private void Travel(string s , int start, IList current, ref List> result)
{
	if(start == s.Length)
	{
		result.Add(new List(current));
		return;
	}
	
	for(var i = start + 1; i <= s.Length; i++)
	{
		var x = s.Substring(start, i - start);
		if(IsP(x)){
			current.Add(x);
			Travel(s, i , current, ref result);
			current.RemoveAt(current.Count - 1);
		}
	}
}




private bool IsP(string s)
{
	if(s.Length == 1){
		return true;
	}
	
	var len = s.Length % 2 == 0 ? s.Length / 2 : (s.Length - 1) / 2;
	
	for(var i = 0;i < len; i++){
		if(s[i] != s[s.Length - 1- i]){
			return false;
		}
	}
	
	return true;
}
}