Given a strings, partitionssuch that every substring of the partition is a palindrome.

Return all possible palindrome partitioning ofs.

For example, givens="aab",
Return

[
  ["aa","b"],
  ["a","a","b"]
]

tag: backtracking, DFS

class Solution {
    public List<List<String>> partition(String s) {
        Map<String, List<List<String>>> hash = new HashMap<>();
        if (s == null || s.length() == 0){
            List<String> empty = new ArrayList<>();
            List<List<String>> temp = new ArrayList<>();
            temp.add(empty);
            return temp;
        }
        if (hash.containsKey(s) && hash.get(s).size() > 0){
            return hash.get(s);
        }

        List<List<String>> cur = new ArrayList<>();
        for (int k = s.length() - 1; k >= 0; k--){
            String postFix = s.substring(k);
            if (isValid(postFix)){
                for (List<String> list : partition(s.substring(0, k))){
                    List<String> copy = new ArrayList<>(list);
                    copy.add(postFix);
                    cur.add(copy);
                }
            }
        }

        hash.put(s, cur);

        return cur;
    }

    private boolean isValid(String str){
        if (str == null || str.length() == 0) return true;
        int i = 0, j = str.length() - 1;

        while (i < j){
            if (str.charAt(i) != str.charAt(j)) return false;
            i++;
            j--;
        }

        return true;
    }
}