Leetcode 131 Palindrome Partitioning(DFS思路)

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


解题思路:

这种返回所有情况blabla的。。一般都用DFS的思路啊。。

三个函数: 一个就是Leetcode自带的那个, 一个是判断是否palindrome的, 一个是做DFS循环的~

 1 public ArrayList<ArrayList<String>> partition(String s) {　　// Leetcode 自带的函数
 2         ArrayList<ArrayList<String>> all = new ArrayList<ArrayList<String>>();
 3         ArrayList<String> al = new ArrayList<String>();
 4         dfs(s, 0, al, all);
 5         return all;
 6     }
 7     
 8     public boolean ifPalindrome(String s){　　//判断回文的
 9         int index_1 = 0;
10         int index_2 = s.length() - 1;
11         while(index_1 < index_2){
12             if(s.charAt(index_1) != s.charAt(index_2))
13                 return false;
14             index_1++;
15             index_2--;
16             
17         }
18         return true;
19     }
20     
21     public void dfs(String s, int start, ArrayList<String> al,  ArrayList<ArrayList<String>> all){　　// DFS
22         if(start == s.length()){　　// 跳出DFS状态的condition
23             ArrayList<String> temp = new ArrayList<String>(al);　　
24             all.add(temp);
25             return;
26         }
27         for(int i = start + 1; i <= s.length(); i++){
28             String str = s.substring(start, i);
29             if(ifPalindrome(str)){
30                 al.add(str);
32                 dfs(s, i, al, all);
33                 al.remove(al.size() - 1);
34             }
35         }
36     }