LeetCode 139. Word Break

word-break.java

/**
 * https://leetcode.com/problems/word-break/
 *
 * O(n * m) runtime, O(n) space
 *   where n is the length of the string, and m is the length of the longest string in the dictionary
 *
 * use DP to solve this question
 *
 * 1. state
 *   state[i] means that if the first i characters of the string can be built using strings in the dictionary
 * 2. function
 *   state[i] is true when there is a string whose length is l in the dictionary
 *   s.t. state[i-l] is true and it matches the related substring
 * 3. initialization
 *   state[0] is true
 * 4. answer
 *   state[n]
 *
 * note that use Set's contains() instead of String's equals() to compare strings to reduce the runtime
 */

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        boolean[] cache = new boolean[s.length()+1];
        cache[0] = true;
        int maxLen = getMaxLength(wordDict);
        for (int i = 1; i <= s.length(); i++) {
            for (int len = maxLen; len >= 1; len--) {
                if (i - len >= 0 && cache[i-len] && wordDict.contains(s.substring(i - len, i))) {
                    cache[i] = true;
                }
            }
        }
        return cache[s.length()];
    }
    
    private int getMaxLength(Set<String> wordDict) {
        int ans = 0;
        for (String str : wordDict) {
            ans = Math.max(ans, str.length());
        }
        return ans;
    }
}