Word Break I Examples:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Example 1:
  s = "leetcode"
  wordDict = ["leet", "code"]
  Output: true
  Explanation: "leetcode" = "leet" + "code"
 
Example 2:
  s = "applepenapple"
  wordDict = ["apple", "pen"]
  Output: true
  Explanation: "applepenapple" = "apple" + "pen" + "apple"
  Note: Words can be reused
 
Example 3:
  s = "catsandog"
  wordDict = ["cats", "dog", "sand", "and", "cat"]
  Output: false
  Explanation: "og" cannot be formed from dictionary words
 
Example 4:
  s = "aaaaaaa"
  wordDict = ["aaaa", "aaa"]
  Output: true
  Explanation: "aaaaaaa" = "aaaa" + "aaa" or "aaa" + "aaaa"
 
 
Word Break II Examples:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Example 1:
  s = "catsanddog"
  wordDict = ["cat", "cats", "and", "sand", "dog"]
  Output: ["cats and dog", "cat sand dog"]
 
Example 2:
  s = "pineapplepennapple"
  wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
  Output: ["pine apple pen apple", "pineapple pen apple", "pine applepen apple"]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

def word_break_brute_force(s: str, word_dict: list[str]) -> bool:
    """
    Brute force word break - DO NOT USE IN PRODUCTION.
    
    Time Complexity: O(2^n) where n = len(s)
                     Each position is a binary choice: break here or not
    Space Complexity: O(n) for recursion stack
    
    Why it's slow:
    - Explores ALL possible segmentations
    - Repeats work for the same suffixes
    - No memoization of results
    """
    word_set = set(word_dict)  # O(1) lookup
    
    def can_break(start: int) -> bool:
        # Base case: reached end of string
        if start == len(s):
            return True
        
        # Try every possible first word
        for end in range(start + 1, len(s) + 1):
            prefix = s[start:end]
            
            if prefix in word_set:
                # If this prefix is valid, try to break the rest
                if can_break(end):
                    return True
        
        return False
    
    return can_break(0)
 
 
# Why is this O(2^n)?
#
# Consider s = "aaaaaaaaaa" (10 'a's), wordDict = ["a", "aa", "aaa", ...]
#
# At each position, we can choose to break or continue.
# This creates a binary decision tree of depth n.
#
# Recursion tree (simplified):
#
#                    can_break(0)
#                   /     |     \
#           [a]break   [aa]break  [aaa]break  ...
#              |          |          |
#        can_break(1) can_break(2) can_break(3)
#           /  |  \       ...        ...
#          ...
#
# Without memoization, we compute can_break(5) from multiple paths:
# - can_break(0) → can_break(1) → ... → can_break(5)
# - can_break(0) → can_break(2) → ... → can_break(5)
# - can_break(0) → can_break(3) → ... → can_break(5)
#
# This duplication leads to exponential time!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

def word_break_dp(s: str, word_dict: list[str]) -> bool:
    """
    Dynamic Programming solution for Word Break.
    
    Time Complexity: O(n² × m) where n = len(s), m = avg word check time
                     With hash set, m = O(1) average, so O(n²)
    Space Complexity: O(n) for dp array + O(k) for word set
                     where k = total characters in dictionary
    """
    if not s:
        return True
    if not word_dict:
        return False
    
    word_set = set(word_dict)  # O(1) lookup
    n = len(s)
    
    # dp[i] = True means s[0:i] can be segmented
    dp = [False] * (n + 1)
    dp[0] = True  # Empty string is breakable
    
    # Fill dp table
    for i in range(1, n + 1):
        for j in range(i):
            # If s[0:j] is breakable AND s[j:i] is a word
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break  # Found one valid segmentation, no need to continue
    
    return dp[n]
 
 
# Optimized version using max word length
def word_break_dp_optimized(s: str, word_dict: list[str]) -> bool:
    """
    Optimized DP that limits inner loop to max word length.
    
    Time: O(n × L²) where L = max word length
          Much better when L << n
    """
    if not s:
        return True
    if not word_dict:
        return False
    
    word_set = set(word_dict)
    max_len = max(len(word) for word in word_dict)
    n = len(s)
    
    dp = [False] * (n + 1)
    dp[0] = True
    
    for i in range(1, n + 1):
        # Only check substrings up to max_len before i
        for j in range(max(0, i - max_len), i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    
    return dp[n]
 
 
# Trace for s = "leetcode", wordDict = ["leet", "code"]:
#
# Initial: dp = [T, F, F, F, F, F, F, F, F]
#               i= 0  1  2  3  4  5  6  7  8
#
# i=1: Try s[0:1]="l" → not in dict
#      dp unchanged
#
# i=2: Try s[0:2]="le", s[1:2]="e" → neither in dict
#      dp unchanged
#
# i=3: Try s[0:3]="lee", etc. → none in dict
#      dp unchanged
#
# i=4: Try s[0:4]="leet" → IN DICT! AND dp[0]=True
#      dp[4] = True
#      dp = [T, F, F, F, T, F, F, F, F]
#
# i=5,6,7: Similar checks, none succeed
#
# i=8: Try s[4:8]="code" → IN DICT! AND dp[4]=True
#      dp[8] = True
#
# Return dp[8] = True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

class TrieNode:
    """Trie node for word break optimization."""
    __slots__ = ['children', 'is_word']
    
    def __init__(self):
        self.children: dict[str, 'TrieNode'] = {}
        self.is_word: bool = False
 
 
class WordBreakTrie:
    """
    Trie-optimized Word Break solution.
    
    Build Time: O(sum of word lengths)
    Query Time: O(n²) worst case, often O(n × L) average
    Space: O(total dictionary characters)
    """
    
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        """Insert a word into the trie."""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True
    
    def word_break(self, s: str) -> bool:
        """
        Check if s can be segmented using trie.
        
        Uses DP where dp[i] = True if s[0:i] is breakable.
        For each position, traverse trie to find all words starting there.
        """
        if not s:
            return True
        
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        
        for i in range(n):
            if not dp[i]:
                continue  # Can't break s[0:i], skip
            
            # Traverse trie starting from s[i]
            node = self.root
            for j in range(i, n):
                char = s[j]
                
                if char not in node.children:
                    break  # No word has this prefix
                
                node = node.children[char]
                
                if node.is_word:
                    # s[i:j+1] is a word, mark dp[j+1] as breakable
                    dp[j + 1] = True
        
        return dp[n]
 
 
def word_break_trie(s: str, word_dict: list[str]) -> bool:
    """
    Main function using trie-optimized word break.
    """
    trie = WordBreakTrie()
    for word in word_dict:
        trie.insert(word)
    return trie.word_break(s)
 
 
# Trie traversal visualization for s = "leetcode":
#
# Build trie with ["leet", "code"]:
#
#     (root)
#       /  \
#      l    c
#      |    |
#      e    o
#      |    |
#      e    d
#      |    |
#      t*   e*
#
# Word break with DP:
#
# i=0, dp[0]=True:
#   j=0: s[0]='l' → in trie, continue
#   j=1: s[1]='e' → in trie, continue
#   j=2: s[2]='e' → in trie, continue
#   j=3: s[3]='t' → in trie, is_word=True → dp[4]=True
#   j=4: s[4]='c' → NOT in current node's children, break
#
# i=1,2,3: dp[i]=False, skip
#
# i=4, dp[4]=True:
#   j=4: s[4]='c' → in trie (from root), continue
#   j=5: s[5]='o' → in trie, continue
#   j=6: s[6]='d' → in trie, continue
#   j=7: s[7]='e' → in trie, is_word=True → dp[8]=True
#
# Return dp[8] = True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

def word_break_ii(s: str, word_dict: list[str]) -> list[str]:
    """
    Word Break II: Return all possible segmentations.
    
    Time Complexity: O(2^n × n) worst case (exponential segmentations)
                     In practice, much faster with memoization
    Space Complexity: O(2^n × n) for storing all results
    
    Strategy:
    1. First, check if ANY segmentation exists (Word Break I)
    2. If yes, use backtracking with memoization to find all
    """
    word_set = set(word_dict)
    
    # Step 1: Precompute which positions are reachable
    # This avoids exploring dead ends
    n = len(s)
    can_reach_end = [False] * (n + 1)
    can_reach_end[n] = True  # End position is reachable
    
    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n + 1):
            if s[i:j] in word_set and can_reach_end[j]:
                can_reach_end[i] = True
                break
    
    # If start position can't reach end, no solution exists
    if not can_reach_end[0]:
        return []
    
    # Step 2: Backtracking with memoization
    memo: dict[int, list[list[str]]] = {}
    
    def backtrack(start: int) -> list[list[str]]:
        """
        Returns all possible ways to segment s[start:].
        Each way is a list of words.
        """
        if start == n:
            return [[]]  # One way: empty list (base case)
        
        if start in memo:
            return memo[start]
        
        result = []
        
        for end in range(start + 1, n + 1):
            word = s[start:end]
            
            if word in word_set and can_reach_end[end]:
                # This word is valid AND we can reach the end from here
                suffix_ways = backtrack(end)
                
                for suffix in suffix_ways:
                    result.append([word] + suffix)
        
        memo[start] = result
        return result
    
    # Get all segmentations and format as strings
    segmentations = backtrack(0)
    return [' '.join(words) for words in segmentations]
 
 
# Trie-optimized version
def word_break_ii_trie(s: str, word_dict: list[str]) -> list[str]:
    """
    Word Break II using trie for efficient word detection.
    """
    # Build trie
    root = {}
    END = '#'
    
    for word in word_dict:
        node = root
        for char in word:
            node = node.setdefault(char, {})
        node[END] = word  # Store word at end node
    
    # Check reachability (reverse DP)
    n = len(s)
    can_reach_end = [False] * (n + 1)
    can_reach_end[n] = True
    
    for i in range(n - 1, -1, -1):
        node = root
        for j in range(i, n):
            if s[j] not in node:
                break
            node = node[s[j]]
            if END in node and can_reach_end[j + 1]:
                can_reach_end[i] = True
                break
    
    if not can_reach_end[0]:
        return []
    
    # Backtracking with trie
    result = []
    path = []
    
    def backtrack(start: int) -> None:
        if start == n:
            result.append(' '.join(path))
            return
        
        node = root
        for j in range(start, n):
            if s[j] not in node:
                break
            node = node[s[j]]
            if END in node and can_reach_end[j + 1]:
                path.append(node[END])
                backtrack(j + 1)
                path.pop()
    
    backtrack(0)
    return result
 
 
# Example trace for s = "catsanddog":
#
# Word dict: ["cat", "cats", "and", "sand", "dog"]
#
# Reachability check (right to left):
#   can_reach_end[10] = True (end)
#   i=7: "dog" in dict, can_reach_end[10] → can_reach_end[7] = True
#   i=4: "and" in dict, can_reach_end[7] → can_reach_end[4] = True
#       "sand" in dict → not needed, already True
#   i=3: "sand" in dict, can_reach_end[7] → can_reach_end[3] = True
#   i=0: "cat" in dict, can_reach_end[3] → can_reach_end[0] = True
#       "cats" in dict, can_reach_end[4] → can_reach_end[0] = True (already)
#
# Backtracking:
#   start=0: "cat" valid, go to start=3
#     start=3: "sand" valid, go to start=7
#       start=7: "dog" valid, go to start=10 → FOUND: "cat sand dog"
#   start=0: "cats" valid, go to start=4
#     start=4: "and" valid, go to start=7
#       start=7: "dog" valid, go to start=10 → FOUND: "cats and dog"
#
# Result: ["cat sand dog", "cats and dog"]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

def min_word_break(s: str, word_dict: list[str]) -> int:
    """
    Find minimum number of words to segment s.
    
    Returns -1 if s cannot be segmented.
    
    Time: O(n² × L) where L = avg word length
    Space: O(n)
    """
    word_set = set(word_dict)
    n = len(s)
    
    # dp[i] = minimum words to segment s[0:i], or infinity if impossible
    INF = float('inf')
    dp = [INF] * (n + 1)
    dp[0] = 0  # Empty string needs 0 words
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] < INF and s[j:i] in word_set:
                dp[i] = min(dp[i], dp[j] + 1)
    
    return dp[n] if dp[n] < INF else -1
 
 
def weighted_word_break(s: str, word_scores: dict[str, int]) -> int:
    """
    Find maximum score segmentation.
    
    word_scores: dictionary mapping words to their scores
    
    Time: O(n² × L)
    Space: O(n)
    """
    n = len(s)
    
    # dp[i] = max score for s[0:i], -infinity if impossible
    NEG_INF = float('-inf')
    dp = [NEG_INF] * (n + 1)
    dp[0] = 0
    
    for i in range(1, n + 1):
        for j in range(i):
            word = s[j:i]
            if word in word_scores and dp[j] > NEG_INF:
                dp[i] = max(dp[i], dp[j] + word_scores[word])
    
    return dp[n] if dp[n] > NEG_INF else -1
 
 
# Example usage:
# word_scores = {"leet": 10, "code": 20, "leetcode": 25}
# weighted_word_break("leetcode", word_scores)
# 
# dp[4] = dp[0] + 10 = 10 ("leet")
# dp[8] = max(dp[0] + 25, dp[4] + 20) = max(25, 30) = 30
#
# Best segmentation: "leet" + "code" = 30 > "leetcode" = 25