139. Word Break

[Shawngbk]

public class Solution { public boolean wordBreak(String s, Set wordDict) { boolean[] dp = new boolean[s.length()+1]; int maxLen = 0; for(String str: wordDict) { maxLen = Math.max(maxLen, str.length()); }

    for(int end = 1; end <= s.length(); end++) {
        if(wordDict.contains(s.substring(0, end))) {
            dp[end] = true;
            continue;
        }
        //Here the starting value of i is optimized from 1 to end-maxLen>1?end-maxLen:1 
   //since the difference between i and end cannot be bigger than the maximum length of string in the dictionary.
   // If it is set to 1, it will waste a lot of time on computing meaningless i values.
        for(int i = end-maxLen>1 ? end-maxLen : 1; i < end; i++) {
            if(dp[i] == true && wordDict.contains(s.substring(i, end))) {
                dp[end] = true;
                break;
            }
        }
    }
    if(dp[s.length()] == true)
    return true;
    else
    return false;
}

}

[Shawngbk]