[LeetCode] Palindrome Partitioning

Problem:

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"]
  ]

Solution:O(n)

public class Solution {
    Map <String, Boolean> map= new HashMap<String,Boolean>();
    public ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> ret = new ArrayList<>();
        helper(ret, new ArrayList<String>(), s);
        return ret;
    }
    public void helper(ArrayList<ArrayList<String>> ret, ArrayList<String>buf, String s){
        if(s.length()==0) {
            ret.add(buf);
            return;
        }
        for(int i =1;i<=s.length();i++){
            String str = s.substring(0,i);
            if(isPali(str)){
                ArrayList<String>nbuf =new ArrayList<String>(buf);
                nbuf.add(str);
                helper(ret, nbuf,s.substring(i));
            }
        }
    }
    public boolean isPali(String s){
        if(map.containsKey(s)) return map.get(s);
        int i = 0,j=s.length()-1;
        while(i<j)
            if(s.charAt(i++)!=s.charAt(j--)){
                map.put(s, false);
                return false;
            }
        map.put(s,true);
        return true;
    }
}