文字列区切り
タイトル:
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 =
コード:
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"]
]
コード:
public class Solution {
public ArrayList<ArrayList<String>> partition(String s) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<ArrayList<String>> list = null;
int len = s.length();
boolean[][] isPalin = new boolean[len][len];
for(int i=0;i<len;i++){
for(int j=0;j<=i;j++){
if(s.charAt(i) == s.charAt(j) && (i-j < 2 || isPalin[j+1][i-1])){
isPalin[j][i] = true;
}
}
}
list = result(s,isPalin,0,len);
for(ArrayList<String> l : list){
Collections.reverse(l);
}
return list;
}
public ArrayList<ArrayList<String>> result(String s,boolean[][] isPalin,int start,int max){
if(start >= max){
ArrayList<String> l = new ArrayList<String>();
ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>();
list.add(l);
return list;
}
ArrayList<ArrayList<String>> all = new ArrayList<ArrayList<String>>();
for(int i=start;i<max;i++){
if(isPalin[start][i]){
ArrayList<ArrayList<String>> list = result(s,isPalin,i+1,max);
String temp = s.substring(start,i+1);
for(ArrayList<String> l : list)
l.add(temp);
all.addAll(list);
}
}
return all;
}
}