EEPW论坛

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

题意：输出所有符合回文字符串；

1. class Solution  

2. {  

3. public:  

4.     vector<vector<string>>res;  

5.     vector<string> tmp;  

6.     //判断是否是回文串  

7.     bool IsHuiWen(string s)  

8.     {  

9.         bool flag = true;  

10.         int left = 0;  

11.         int right = s.size() - 1;  

12.   

13.         while (left <= right)  

14.         {  

15.             if (s[left] != s[right])  

16.             {  

17.                 flag = false;  

18.                 break;  

19.             }  

20.   

21.             left++;  

22.             right--;  

23.         }  

24.   

25.         return flag;  

26.     }  

27.   

28.     void dfs(string s, int pos)  

29.     {  

30.         if (pos >= s.size())  

31.         {  

32.             res.push_back(tmp);  

33.             return;  

34.         }  

35.   

36.         for (int i = 1; i <= s.size() - pos; i++)  

37.         {  

38.             string sub = s.substr(pos, i);  

39.             if (IsHuiWen(sub))  

40.             {  

41.                 tmp.push_back(sub);  

42.                 dfs(s, pos + i);  

43.                 tmp.pop_back();  

44.             }  

45.         }  

46.     }  

47.   

48.     vector<vector<string>> partition(string s)  

49.     {  

50.         dfs(s, 0);  

51.         return res;  

52.     }  

53. };