Question:

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”.

Thinking:

This question can be solved in dynamic programming. We can get parts of the string once and check if it’s in the dictionary words and then check the left. And we can store the result of previous substring with index in the array.

Solution:

public boolean wordBreak(String s, Set<String> wordDict) {
    boolean[] valid = new boolean[s.length()+1];

    valid[0] = true;

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

    return valid[s.length()];

Reference: https://leetcode.com/discuss/18904/java-implementation-using-dp-in-two-ways