Word Break

https://leetcode.com/problems/word-break/\#/description

isValid[i] denotes if s.subtstring(0, i) is wordbreakable.

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] isValid = new boolean[s.length() + 1];
        // isValid[i] denotes if s.subtstring(0, i) is wordbreakable.

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

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

Improved inner loop

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] isValid = new boolean[s.length() + 1];
        // isValid[i] denotes if s.subtstring(0, i) is wordbreakable.

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

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

Improved version, get the max length of word in wordDict to reduce inner loop times.

public class Solution {
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */
    public boolean wordBreak(String s, Set<String> wordDict) {
        // write your code here
        boolean[] isValid = new boolean[s.length() + 1];
        int maxLen = getMaxLength(wordDict);
        isValid[0] = true;
        for(int i = 1; i <= s.length(); i++){
            for(int j = i-1 ; j >= Math.max(0, i - maxLen); j--){
                if(isValid[j] && wordDict.contains(s.substring(j, i))){
                    isValid[i] = true;
                    break;
                }
            }
        }

        return isValid[s.length()];
    }

    private int getMaxLength(Set<String> dict) {
        int maxLength = 0;
        for (String word : dict) {
            maxLength = Math.max(maxLength, word.length());
        }
        return maxLength;
    }

}