AC-ed after using a cache


  • 1
    K

    my code had a time limit error when only using recursive function dfs. After reading someone else's code, used a cache to store already computed function, got AC-ed.

        HashMap<Integer, List<String>> cache = new HashMap<Integer, List<String>>();
    
    public List<String> dfs(ArrayList<ArrayList<Integer>> DP, String str, int startidx){
        if(cache.containsKey(startidx)) return cache.get(startidx);
        ArrayList<Integer> dplist = DP.get(startidx);
        ArrayList<String> retlist = new ArrayList<String>();
        for(int i = 0; i < dplist.size(); i++){
            int j = dplist.get(i);
            String substr = str.substring(startidx, j);
            if(j == str.length())
                retlist.add(substr);
            else{
                List<String> temp = dfs(DP, str, j);
                for(int k = 0; k < temp.size(); k++)
                    retlist.add(substr + " " + temp.get(k));
            }
        }
        if(cache.containsKey(startidx) == false){
            cache.put(startidx, retlist);
        }
        return retlist;
    }
    
    public List<String> wordBreak(String s, Set<String> dict) {
        ArrayList<ArrayList<Integer>> DP = new ArrayList<ArrayList<Integer>>();
        for(int i = 0; i < s.length(); i++) {
            ArrayList<Integer> dplist = new ArrayList<Integer>();
            for (int j = i + 1; j <= s.length(); j++)
                if (dict.contains(s.substring(i, j))){
                    dplist.add(j);
                }
            DP.add(dplist);
        }
        return this.dfs(DP, s, 0);
    }

Log in to reply
 

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