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"]
]
這個(gè)題目就是在每一次尋找完第一個(gè)回文串，然后在剩下的字符串中又是找到第一個(gè)回文串香到，一直這樣到最后一個(gè)鱼冀。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Solution131 {
static LinkedList<List<String>> ans = new LinkedList<List<String>>();
public List<List<String>> partition(String s) {
ans.clear();
LinkedList<String> list = new LinkedList<String>();
helper(s + "*", list, 0);
return ans;
}
private void helper(String s, LinkedList<String> list1, int n) {
if (s.equals("*") || s.equals(" ") || s == null) {
List<String> list2 = new ArrayList<String>();
for (String string : list1) {
list2.add(string);
}
ans.add(list2);
return;
}
for (int i = 1; i < s.length(); i++) {
String cur = s.substring(0, i);
String res = s.substring(i, s.length());
if (isPartitioning(cur)) {
list1.add(cur);
helper(res, list1, n + 1);
list1.pollLast();
}
}
}
private boolean isPartitioning(String cur) {
String cur1 = new StringBuffer(cur.trim()).reverse().toString();
return cur.equals(cur1);
}
public static void main(String[] args) {
new Solution131().partition("aab");
System.out.println(ans);
}
}
這個(gè)和分ip的是一樣的
