Trie

68. Implement Trie (Prefix Tree)

TODO

69. 139. Word Break

[DP] Building up DP intuition with 3 solutions: Recursive, Memoization and Tabulation

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //final Boolean[] cache = new Boolean[s.length()];
        //return memorized(0, s, wordDict, cache);
        return dp(s, wordDict);
    }

    private boolean recursive(final int i, final String s, final List<String> wordDict) {
        if (i >= s.length()) {
            return true;
        }

        for (int j = i; j < s.length(); j++) {
            if (wordDict.contains(s.substring(i, j+1)) && recursive(j+1, s, wordDict)) {
                return true;
            }
        }

        return false;
    }

    private boolean memorized(final int i, final String s, final List<String> wordDict, final Boolean[] cache) {
        if (i >= s.length()) {
            return true;
        }

        if (cache[i] != null)
            return cache[i];

        for (int j = i; j < s.length(); j++) {
            if (wordDict.contains(s.substring(i, j+1)) && memorized(j+1, s, wordDict, cache)) {
                cache[i] = true;
                return true;
            }
        }
        
        cache[i] = false;
        return false;
    }

    private boolean dp(final String s, final List<String> wordDict) {
        final boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

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