LeetCode - Word Break

WordBreak.java

// backtracking : time limit exceeded
public boolean wordBreak(String s, Set<String> wordDict) {
        if(s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) return false;
        return helper(0, s, wordDict);
    }
    
    public boolean helper(int p, String s, Set<String> wordDict){
        if(p == s.length()) return true;
        
        for(int i=p+1; i<=s.length(); i++){
            String subStr = s.substring(p, i);
            if(wordDict.contains(subStr)){
                if(helper(i, s, wordDict)){    // return helper(i, s, wordDict);  failed case: "aaaaaaa", ["aaaa", "aaa"]
                    return true;
                }
            }
        }
        return false;
    }
    
// dynamic programming
public boolean wordBreak(String s, Set<String> wordDict) {
        if(s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) return false;
        // ret[i] represents if substring(0, i) is valid word break
        boolean[] ret = new boolean[s.length()+1];
        ret[0] = true;
        for(int i = 1; i <= s.length(); i++){
            for(int j=0; j <= i; j++){
                if(ret[j] && wordDict.contains(s.substring(j, i))){
                    ret[i] = true;
                    break;
                }
            }
        }
        return ret[s.length()];
    }