Palindrome Partitioning

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;}
   
}