Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

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

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

public boolean wordBreak(String s, Set<String> wordDict) {
    if(wordDict.contains(s)){ return true;}
    boolean[] dp = new boolean[s.length()];
    dp[0] = true;
    for(int i = 1; i < s.length(); i++){
        if(wordDict.contains(s.substring(0, i))){
            dp[i] = true;
        }
        else{
            for(int j = i - 1; j >= 0; j--){
                if(wordDict.contains(s.substring(j, i)) && dp[j]){
                    dp[i] = true;
                    break;
                }
            }
        }
        if(dp[i] && wordDict.contains(s.substring(i, s.length()))){
            return true;
        }
    }
    return false;
}

results matching ""

    No results matching ""