[131. Palindrome Partitioning] #leetcode

131_0915.java

class Solution {
  // O(n!) O(n!)
    private List<List<String>> res = new ArrayList<List<String>>();
    private HashMap<String, Boolean> ps = new HashMap<String, Boolean>();
        
    public List<List<String>> partition(String s) {
        findP(s, new ArrayList<String>());
        return res;
    }
    
    private void findP(String s, List<String> current){
        if (s.length() == 0) {
            res.add(new ArrayList<String>(current));
            return;
        }
        
        int n = s.length();
        for (int i = 1; i <= n; i++) {
            String left = s.substring(0, i);
            String right = s.substring(i);
            if (isP(left)) {
                current.add(left);
                findP(right, current);
                current.remove(current.size()-1);
            }
        } 
    }
    
    private boolean isP(String s) {
        if (ps.containsKey(s)) return ps.get(s);
        if (s.length() == 0 || s.length() == 1) return true;
            
        int n = s.length();
        boolean equal = s.charAt(0) == s.charAt(n-1) && isP(s.substring(1, n-1));
        
        ps.put(s, equal);
        return equal;
    }
}