Word Break II

Problem

Word Break II

Approach

1. we can use DFS to check if every substring in s is the word of the Dictionary.
2. More imporantly, it’s necessary to use Memorization to decrease the search time.

Code

class Solution {
    private List<String> dfs(String s, int index, Set<String> set, Map<Integer, List<String>> exist){
        if(index == s.length()){
            List<String> res = new ArrayList<>();
            res.add("");
            return res;
        }
        if(exist.containsKey(index)){
            return exist.get(index);
        }
        List<String> curStr = new ArrayList<>();
        for(int i = index + 1; i <= s.length(); i ++){
            if(set.contains(s.substring(index, i))){
                List<String> nextStr = dfs(s, i, set, exist);
                for(String ns : nextStr){
                    if(ns.equals("")){
                        curStr.add(s.substring(index, i));
                    } else {
                        curStr.add(s.substring(index, i) + " " + ns);
                    }
                }
            }
        }
        exist.put(index, curStr);
        return curStr;
    }
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>();
        for(String w : wordDict){
            set.add(w);
        }
        return dfs(s, 0, set, new HashMap<Integer, List<String>>());
    }
}