首页 > 代码库 > 131. Palindrome Partitioning

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

典型的backtracking题目。需要一个函数来判断是否为回文序列,然后s从头至尾,如果前面的是回文序列,则recursive到s的后半部分。
 public IList<IList<string>> Partition(string s) {        var res  = new  List<IList<string>>();        if(s =="") return res;        Backtracking(s,res,new List<string>());        return res;            }        private void Backtracking(string s, List<IList<string>> res , List<string> cur)    {        if(s == "")        {            res.Add(new List<string>(cur));        }        else        {            for(int i =1;i<= s.Length;i++)            {                if(IsPalindrome(s.Substring(0,i)))                 {                    cur.Add(s.Substring(0,i));                    Backtracking(s.Substring(i),res,cur);                    cur. RemoveAt(cur.Count()-1);                }            }        }    }        private bool IsPalindrome(string s)    {        if(s == null) return false;        var c = s.ToCharArray();        Array.Reverse(c);        return s == new string(c);    }

 

131. Palindrome Partitioning