Got word break2 in one of the interviews
ctci07
121

I started off from what i remember doing
Iterating over list of words , followed by recursion and then memo.

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0) return new ArrayList<>();
        Map<String,List<String>> h = new HashMap<>();
        return dfs(s,wordDict,h);
    }
    List<String> dfs(String s, List<String> words, Map<String,List<String>> h){
        List<String> res = new ArrayList<>();
        if (s.length() == 0){
            res.add("");
            return res;
        }
        if (h.containsKey(s)) return h.get(s);
        for (String word : words){
            if (s.startsWith(word)){
                List<String> sub = dfs(s.substring(word.length()),words, h);
                for (String ss : sub){
                    if (ss.length() == 0){
                        res.add(word);
                    }else{
                        res.add(word+" "+ss);
                    }
                }
            }
        }
        h.put(s,res);
        return res;
    }
}

Interviewer told that wordDict is huge and we cannot iterate but you can use .contains. You can assume that wordDict is set and so use .contains.
So other approach was to run 2 loops like wordbreak1 and use .contains over dict and complete it until we reach end. But this approach does not work when we have complex dict which is a definite possiblity.
eg:Thisisaverygoodexample
[this is a very go good example]
Problem is we substring with 'go' and we are left with 'odexample' and we need to backtrack.
Tried to implement backtrack and ran out of time. Can anyone suggest me what may be the approach.

Comments (1)