Word Break

Time: O(n^2)

Space: O(n)

Intuition

DP: dp[i] = true if s[0..i-1] can be segmented using dictionary words. For each i, check all j < i: if dp[j] is true and s[j..i-1] is in the dictionary, dp[i]=true.

Algorithm

1wordSet = HashSet(dictionary). dp[0]=true.
2For i from 1 to n: for j from 0 to i-1: if dp[j] and s[j..i-1] in wordSet: dp[i]=true. Break.
3Return dp[n].

Example Walkthrough

Input: s="leetcode", dict=["leet","code"]

1.dp[0]=true. i=4: j=0, dp[0]=true, "leet" in dict â†’ dp[4]=true.
2.i=8: j=4, dp[4]=true, "code" in dict â†’ dp[8]=true.

Output: true

Common Pitfalls

•Use a HashSet for O(1) dictionary lookups â€” do not iterate the dictionary for each check.

Word Break.java

Java

// Approach: DP. dp[i] = can s[0..i-1] be segmented using dict? dp[i] = any dp[j] where s[j..i-1] is in dict.
// Time: O(n^2) Space: O(n)
import java.util.*;

class Solution {
    static Trie trie;
    static Boolean[] memo;

    public int wordBreak(String s, String[] dictionary) {
        trie = new Trie();

        for (String word : dictionary)
            trie.insert(word);

        memo = new Boolean[s.length()];
        return canBreak(s, 0) ? 1 : 0;
    }

    private boolean canBreak(String s, int start) {
        if (start == s.length())
            return true;
            
        if (memo[start] != null)
            return memo[start];

        TrieNode node = trie.root;
        for (int i = start; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!node.children.containsKey(c))
                break;

            node = node.children.get(c);
            if (node.isEnd && canBreak(s, i + 1))
                return memo[start] = true;
        }

        return memo[start] = false;
    }
}

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
}

class Trie {
    TrieNode root;

    Trie() {
        root = new TrieNode();
    }

    void insert(String word) {
        TrieNode node = root;

        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }

        node.isEnd = true;
    }

    boolean search(String word) {
        TrieNode node = root;

        for (char c : word.toCharArray()) {
            if (!node.children.containsKey(c))
                return false;
            node = node.children.get(c);
        }

        return node.isEnd;
    }
}

Was this solution helpful?