Given anon-emptystringsand a dictionarywordDictcontaining a list ofnon-emptywords, determine ifscan be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s="leetcode",
dict=["leet", "code"].

Return true because"leetcode"can be segmented as"leet code".

UPDATE (2017/1/4):
ThewordDictparameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

tag: BFS, DFS, DP

DFS

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0) return true;
        return dfs(s, 0, wordDict, new Boolean[s.length()]);
    }

    private boolean dfs(String s, int start, List<String> wordDict, Boolean[] hash){
        if (start == s.length()) return true;
        if (hash[start] != null) return hash[start];


        for (int end = start + 1; end <= s.length(); end++){
            String temp = s.substring(start, end);
            if (wordDict.contains(temp) && dfs(s, end, wordDict, hash)){
                return hash[start] = true;
            }
        }

        return hash[start] = false;

    }
}

DP

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

        for (int i = 1; i <= s.length(); i++){
            for (int j = 0; j < i; j++){
                if (dp[j] && wordDict.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }
}