/*
Runtime: 1 ms, faster than 99.73% of Java online submissions for Word Break.
Memory Usage: 34 MB, less than 100.00% of Java online submissions for Word Break.
*/
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length()];
        Arrays.fill(dp, true);
        return wordBreakImpl(s, 0, dp, wordDict);
    }

    public boolean wordBreakImpl(String s, int offset, boolean[] dp, List<String> wordDict) {
        if (dp[offset]) {
            for (String word : wordDict) {
                if (s.startsWith(word, offset)) {
                    int next = offset + word.length();
                    if (next == s.length() || wordBreakImpl(s, next, dp, wordDict)) {
                        return true;
                    }
                }
            }
            dp[offset] = false;
        }
        return false;
    }
}