Palindrome Partitioning

Palindrome Partitioning.java

public class Solution {
     Map<String,List<List<String>>> cache = new HashMap<String, List<List<String>>>();
    public List<List<String>> partition(String s) {
        
        if(cache.containsKey(s)) {
            return cache.get(s);
        }

        List<List<String>> result = new LinkedList<List<String>>();
        if(isP(s)){
            List<String> l = new LinkedList<String>();
            l.add(s);
            result.add(l);
        }

        if(s.length() == 1){
            cache.put(s,result);
            return result;
        }

        Set<String> seen = new HashSet<String>();
        for(int i=1;i<s.length();i++){
            List<List<String>> left = partition(s.substring(0,i)),
                    right = partition(s.substring(i));

            for(List<String> l:left){
                for(List<String> r:right){
                    List<String> list = new LinkedList<String>();
                    list.addAll(l);
                    list.addAll(r);
                    if(!seen.contains(list.toString())){
                        seen.add(list.toString());
                        result.add(list);
                    }
                }
            }
        }

        cache.put(s,result);
        return result;
    }

    boolean isP(String a){
        if(a.length() % 2 == 0){
            int center = a.length() / 2;
            for(int i=0;center >= i+1;i++){
                if(a.charAt(center + i) != a.charAt(center - 1 - i))
                    return false;
            }
        }

        int center = (a.length() - 1) / 2;
        for(int i=1;center >= i;i++){
            if(a.charAt(center + i) != a.charAt(center - i))
                return false;
        }
        return true;
    }
}