This question is quite difficult to me, since I seldom deal with too many string problems before. Hope more questions related with this one can help me get better at strings in the future.
Anyway, thanks to code_ganker for his good explanation and his code:
http://blog.csdn.net/linhuanmars/article/details/22777711
Actually, my proposed algorithm is very similar to his. But it took me too much time to think of this idea, I believe things will get better for sure if I played with these "dictionary" kind of things more often. My code will be updated later.
Compared with code_ganker's code, mine looks more complicated, less readable. Hope I can improve this in following days.
UPDATE: use a stack instead of recursion. But this method took me too much time to deal with the while loop. At first, I thought this should be similar to DFS case. But one thing I need to be aware of is that "visited" should be restored when elements are popped out, since they will be reused in next loop.
public class Solution {
public List<List<String>> partition(String s) {
int len = s.length();
if(s == null) return null;
LinkedList<List<String>> res = new LinkedList<List<String>>();
LinkedList<String> sub = new LinkedList<String>();
for(int i = 0 ; i<len; i++){
sub.add(String.valueOf(s.charAt(i)));
}
res.add(sub);
if(len <= 1){
return res;
}
ArrayList<ArrayList<Interval>> intervals = new ArrayList<ArrayList<Interval>>();
for(int i = 0;i < len; i ++){
ArrayList<Interval> tmpInterval = new ArrayList<Interval>();
intervals.add(tmpInterval);
int mv = i + 1;
tmpInterval.add(new Interval(i,i));
while(mv < len){
if(isPld(s,i,mv)){
tmpInterval.add(new Interval(i,mv));
}
mv++;
}
}
addPartitions(res,s,intervals);
return res;
}
public boolean isPld(String s, int start, int end){
while(end >= start){
if(s.charAt(end) == s.charAt(start)){
start ++;
end --;
}else return false;
}
return true;
}
public void addPartitions(List<List<String>> res, String s, ArrayList<ArrayList<Interval>> intervals){
int i = 0;
LinkedList<String> tmpPre = new LinkedList<String>();
ArrayList<Interval> tmpIntervals = intervals.get(i);
if(!tmpIntervals.isEmpty()){
for(int j = 0 ; j < i;j++){
tmpPre.add(String.valueOf(s.charAt(j)));
}
// similar to DFS
for(int j = 0; j < tmpIntervals.size();j++){
LinkedList<Interval> stack = new LinkedList<Interval>();
stack.push(tmpIntervals.get(j));
LinkedList<String> tmpRes = new LinkedList<String>();
tmpRes.addAll(tmpPre);
while(!stack.isEmpty()){
boolean allVisited = true;
Interval crntInterval = stack.peek();
if(!crntInterval.visited){
crntInterval.visited = true;
tmpRes.add(s.substring(crntInterval.start, crntInterval.end+1));
// crntInterval.visited = true;
if(crntInterval.end == s.length() - 1){
LinkedList<String> oneRes = new LinkedList<String>();
oneRes.addAll(tmpRes);
if(!res.contains(tmpRes)){
res.add(oneRes);
}
stack.pop().visited = false;
tmpRes.removeLast();
}
else{
for(int n = 0; n < intervals.get(crntInterval.end+1).size(); n++){
if(!intervals.get(crntInterval.end+1).get(n).visited){
stack.push(intervals.get(crntInterval.end+1).get(n));
allVisited = false;
}
}
if(allVisited){
stack.pop().visited = false;
tmpRes.removeLast();
}
}
}
else{
stack.pop().visited = false;
tmpRes.removeLast();
}
}
setToFalse(intervals);
}
}
}
public void setToFalse(ArrayList<ArrayList<Interval>> intervals){
for(int i = 0; i < intervals.size();i++){
ArrayList<Interval> tmp = intervals.get(i);
for(int j = 0; j < tmp.size(); j ++){
tmp.get(j).visited = false;
}
}
}
}
class Interval {
public int start;
public int end;
public boolean visited = false;
Interval(int i, int j){start = i; end = j;}
}
