leetcode131

深度优先遍历（DFS），先判断前一个部分是否是回文，如果是，则将其加进集合中，然后继续判断后面的回文串。

在回溯的时候，将之前加入集合的串删除，重新选择回文串。每到达一次叶子节点，得到一组结果。

public class Solution
    {
        IList<IList<string>> res = new List<IList<string>>();
        public IList<IList<string>> Partition(string s)
        {
            DFS(s, new List<string>());
            return res;
        }

        private void DFS(string s, List<string> list)
        {
            if (s.Length < 1)
            {
                res.Add(new List<string>(list));
                return;
            }
            for (int i = 1; i <= s.Length; i++)
            {
                string str = s.Substring(0, i);
                if (isPalindrom(str))
                {
                    list.Add(str);
                    DFS(s.Substring(i), list);
                    list.RemoveAt(list.Count - 1);
                }
                else
                {
                    continue;
                }
            }
        }
        private bool isPalindrom(String s)
        {       //s必须是》=1的字符串        
            int p1 = 0;
            int p2 = s.Length - 1;
            int len = (s.Length + 1) / 2;
            for (int i = 0; i < len; i++)
            {
                if (s[p1++] != s[p2--])
                {
                    return false;
                }
            }
            return true;
        }
    }

补充一个python的实现：

 1 class Solution:
 2     def isPalindrome(self,s):
 3         n = len(s)
 4         if n == 0:
 5             return False
 6         if n == 1:
 7             return True
 8         mid = n // 2
 9         i,j = mid,mid
10         if n % 2 == 0:
11             i -= 1
12         while i >=0 and j <= n - 1:
13             if s[i] != s[j]:
14                 return False
15             i -= 1
16             j += 1
17         return True
18 
19     def backTrack(self,s,res,temp):
20         if len(s) <= 0:
21             res.append(temp[:])
22             return
23 
24         for i in range(len(s)):
25             sub = s[:i+1]
26             if self.isPalindrome(sub):
27                 temp.append(sub)
28                 self.backTrack(s[i+1:],res,temp)
29                 temp.pop(-1)
30 
31     def partition(self, s: str) -> 'List[List[str]]':
32         res = []
33         self.backTrack(s,res,[])
34         return res