DSA 450 Notes

Problem Statement

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

Example:

Input: s = "leetcode", dictionary = ["leet", "code"]
Output: true ("leetcode" can be segmented as "leet code")

Noob-Friendly Explanation

Imagine you have a long word written without spaces, like "ilikecoding". You also have a dictionary of known words like ["i", "like", "coding", "code"]. Can you insert spaces into the long word so that every piece is a real word from your dictionary? It's like splitting a mashed-together sentence back into proper words.

Approach 1: Brute Force

Intuition

Try every possible way to split the string. For each prefix that matches a dictionary word, recursively check if the remaining suffix can also be broken into dictionary words.

Algorithm

Start from the beginning of the string.
Try every prefix. If a prefix is in the dictionary, recursively check the rest.
If the entire string is consumed, return true.
If no prefix works, return false.

java

import java.util.*;

class Solution {
    public static boolean wordBreakBrute(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        return canBreak(s, dict, 0);
    }

    private static boolean canBreak(String s, Set<String> dict, int start) {
        if (start == s.length()) return true;

        for (int end = start + 1; end <= s.length(); end++) {
            String prefix = s.substring(start, end);
            if (dict.contains(prefix) && canBreak(s, dict, end)) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        String s = "leetcode";
        List<String> dict = Arrays.asList("leet", "code");
        System.out.println(wordBreakBrute(s, dict)); // Output: true
    }
}

Complexity Analysis

Time Complexity: O(2^n) - in the worst case, we try all possible splits
Space Complexity: O(n) - recursion stack depth

Approach 2: Optimal

Intuition

Use a 1D DP array where dp[i] is true if the substring s[0..i-1] can be segmented into dictionary words. For each position, check all possible last words ending at that position.

Algorithm

Create a boolean dp array of size n + 1. Set dp[0] = true (empty string is valid).
For each position i from 1 to n, check all positions j from 0 to i-1.
If dp[j] is true and s[j..i] is in the dictionary, set dp[i] = true.
Return dp[n].

java

import java.util.*;

class Solution {
    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true; // Empty string can always be segmented

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break; // No need to check further for this position
                }
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        String s = "leetcode";
        List<String> dict = Arrays.asList("leet", "code");
        System.out.println(wordBreak(s, dict)); // Output: true

        String s2 = "catsandog";
        List<String> dict2 = Arrays.asList("cats", "dog", "sand", "and", "cat");
        System.out.println(wordBreak(s2, dict2)); // Output: false
    }
}

Complexity Analysis

Time Complexity: O(n^2) - two nested loops plus substring operations
Space Complexity: O(n) - the dp array

Word Break Problem

Problem Statement

Noob-Friendly Explanation

Approach 1: Brute Force

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal

Intuition

Algorithm

Complexity Analysis