Java backtracking solution with memorization


  • 0
    R

    for the simple dfs solution, we recalculated the substring many times, so i just modified it using the memorization to decrease the calculation time. here is my code:

    '''
    public class Solution {

    public List<List<String>> partition(String s) {
        if(s == null || s.length() == 0) return new ArrayList<>();
        HashMap<String, List<List<String>>> cache = new HashMap<>();
        return dfs(s, cache);
    }
    
    public List<List<String>> dfs(String s, HashMap<String, List<List<String>>> cache) {
        if(cache.containsKey(s)) return cache.get(s);
        List<List<String>> res = new ArrayList<>();
        
        for(int i = 0; i < s.length(); i++) {
            String prefix = s.substring(0, i+1);
            if(isPalindrome(prefix)) {
                if(i == s.length() - 1) {
                    List<String> path = new ArrayList<>();
                    path.add(prefix);
                    res.add(path);
                }else{
                   List<List<String>> tmp = dfs(s.substring(i+1), cache); 
                   for(List<String> p : tmp) {
                       List<String> t = new ArrayList<>(p);
                       t.add(0, prefix);
                       res.add(t);
                   }
                }
            }
        }
        
        cache.put(s, res);
        return res;
    }
    
    public boolean isPalindrome(String s) {
        for(int a = 0, b = s.length()-1; a < b; a++, b--) {
            if(s.charAt(a) != s.charAt(b)) return false;
        }
        return true;
    }
    

    }

    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.