Word Break

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

The first argument is a string, A.
The second argument is an array of strings, B.

Return 0 / 1 ( 0 for false, 1 for true ) for this problem.

1 <= len(A) <= 6500
1 <= len(B) <= 10000
1 <= len(B[i]) <= 20

Input 1:
    A = "myinterviewtrainer",
    B = ["trainer", "my", "interview"]

Output 1:
    1

Explanation 1:
    Return 1 ( corresponding to true ) because "myinterviewtrainer" can be segmented as "my interview trainer".
    
Input 2:
    A = "a"
    B = ["aaa"]

Output 2:
    0

Explanation 2:
    Return 0 ( corresponding to false ) because "a" cannot be segmented as "aaa".

Solution:

Time: O(n^3)
Space: O(n)

    public int wordBreak(String A, String[] B) {
        Set<String> dict = new HashSet<>(Arrays.asList(B));
        int n = A.length();
        // dp[i] = work break true for A[0 - i]
        // dp[i] = dp[k] && A[k + 1, i) for k < i
        // dp[n]
        boolean[] dp = new boolean[n];
        for (int i = 0; i < n; i ++) {
            if (dict.contains(A.substring(0, i + 1))) dp[i] = true;
            else {
                for (int k = 0; k < i; k ++) {
                    dp[i] |= dp[k] && dict.contains(A.substring(k + 1, i + 1));
                }
            }
        }
        
        return dp[n - 1] ? 1 : 0;
    }

public class Solution {
    public int wordBreak(String A, String[] B) {
        Set<String> dict = new HashSet<>();
        int n = A.length();
        int maxWordLength = 0;
        for (String s : B) {
            dict.add(s);
            maxWordLength = Math.max(maxWordLength, s.length());
        }
        // dp[i] = work break true for A[0 - i]
        // dp[i] = dp[k] && A[k + 1, i) for k < i
        // dp[n]
        boolean[] dp = new boolean[n];
        for (int i = 0; i < n; i ++) {
            if (dict.contains(A.substring(0, i + 1))) dp[i] = true;
            else {
                for (int k = 0; k < i; k ++) {
                    if (dp[i]) break;
                    if (!dp[k] || i - k > maxWordLength) continue;
                    dp[i] = dict.contains(A.substring(k + 1, i + 1));
                }
            }
        }
        
        return dp[n - 1] ? 1 : 0;
    }
}

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