[AlgoMastery]
Topics›String›Word Break Problems
📖

Word Break Problems

String
~20 min read
5 practice problems

Overview

Word Break Problems involve determining if a string can be segmented into words from a dictionary, or finding all possible segmentations. These problems test your understanding of dynamic programming, backtracking, and string manipulation.

Key challenges:

  • Checking if segmentation is possible
  • Finding all possible segmentations
  • Optimizing with memoization
  • Handling overlapping subproblems
  • Space-efficient solutions

Common word break problems include:

  • Check if word break is possible
  • Find all word break combinations
  • Word break II (all sentences)
  • Concatenated words
  • Word break with constraints

Pattern 1: Basic Word Break

Check if string can be segmented into dictionary words.

Dynamic Programming approach:

function wordBreak(s: string, wordDict: string[]): boolean {
  const wordSet = new Set(wordDict);
  const n = s.length;
  const dp: boolean[] = new Array(n + 1).fill(false);
  dp[0] = true; // Empty string is valid
  
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  
  return dp[n];
}

Time: O(n^2), Space: O(n)

Optimized with word length check:

function wordBreakOptimized(s: string, wordDict: string[]): boolean {
  const wordSet = new Set(wordDict);
  const maxLen = Math.max(...wordDict.map(w => w.length));
  const n = s.length;
  const dp: boolean[] = new Array(n + 1).fill(false);
  dp[0] = true;
  
  for (let i = 1; i <= n; i++) {
    for (let j = Math.max(0, i - maxLen); j < i; j++) {
      if (dp[j] && wordSet.has(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  
  return dp[n];
}

Time: O(n * m) where m is max word length, Space: O(n)

Pattern 2: Word Break II (All Sentences)

Find all possible sentences by adding spaces.

function wordBreakII(s: string, wordDict: string[]): string[] {
  const wordSet = new Set(wordDict);
  const memo = new Map<number, string[]>();
  
  const backtrack = (start: number): string[] => {
    if (start === s.length) {
      return [''];
    }
    
    if (memo.has(start)) {
      return memo.get(start)!;
    }
    
    const results: string[] = [];
    
    for (let end = start + 1; end <= s.length; end++) {
      const word = s.substring(start, end);
      
      if (wordSet.has(word)) {
        const subResults = backtrack(end);
        
        for (const subResult of subResults) {
          if (subResult === '') {
            results.push(word);
          } else {
            results.push(word + ' ' + subResult);
          }
        }
      }
    }
    
    memo.set(start, results);
    return results;
  };
  
  return backtrack(0);
}

Time: O(2^n) worst case, Space: O(2^n)

With early termination:

function wordBreakIIOptimized(s: string, wordDict: string[]): string[] {
  const wordSet = new Set(wordDict);
  const maxLen = Math.max(...wordDict.map(w => w.length));
  
  // First check if word break is possible
  const canBreak = wordBreak(s, wordDict);
  if (!canBreak) return [];
  
  const memo = new Map<number, string[]>();
  
  const backtrack = (start: number): string[] => {
    if (start === s.length) return [''];
    if (memo.has(start)) return memo.get(start)!;
    
    const results: string[] = [];
    
    for (let end = start + 1; end <= Math.min(s.length, start + maxLen + 1); end++) {
      const word = s.substring(start, end);
      
      if (wordSet.has(word)) {
        const subResults = backtrack(end);
        
        for (const subResult of subResults) {
          results.push(subResult === '' ? word : word + ' ' + subResult);
        }
      }
    }
    
    memo.set(start, results);
    return results;
  };
  
  return backtrack(0);
}

Pattern 3: Word Break with Trie

Use Trie for efficient word matching.

class TrieNode {
  children: Map<string, TrieNode>;
  isEnd: boolean;
  
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class Trie {
  root: TrieNode;
  
  constructor(words: string[]) {
    this.root = new TrieNode();
    for (const word of words) {
      this.insert(word);
    }
  }
  
  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEnd = true;
  }
}

function wordBreakWithTrie(s: string, wordDict: string[]): boolean {
  const trie = new Trie(wordDict);
  const n = s.length;
  const dp: boolean[] = new Array(n + 1).fill(false);
  dp[0] = true;
  
  for (let i = 0; i < n; i++) {
    if (!dp[i]) continue;
    
    let node = trie.root;
    for (let j = i; j < n; j++) {
      const char = s[j];
      if (!node.children.has(char)) break;
      
      node = node.children.get(char)!;
      if (node.isEnd) {
        dp[j + 1] = true;
      }
    }
  }
  
  return dp[n];
}

Time: O(n^2), Space: O(n + m) where m is total dict length

Pattern 4: Concatenated Words

Find all words that can be formed by concatenating other words.

function findAllConcatenatedWordsInADict(words: string[]): string[] {
  const wordSet = new Set(words);
  const results: string[] = [];
  
  for (const word of words) {
    if (canForm(word, wordSet)) {
      results.push(word);
    }
  }
  
  return results;
}

function canForm(word: string, wordSet: Set<string>): boolean {
  const n = word.length;
  const dp: boolean[] = new Array(n + 1).fill(false);
  dp[0] = true;
  
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j]) {
        const subWord = word.substring(j, i);
        // Don't count the word itself
        if (wordSet.has(subWord) && subWord !== word) {
          dp[i] = true;
          break;
        }
      }
    }
  }
  
  return dp[n];
}

Time: O(n * m^2) where n is words count, m is avg length, Space: O(m)

With memoization:

function findAllConcatenatedWordsMemoized(words: string[]): string[] {
  const wordSet = new Set(words);
  const memo = new Map<string, boolean>();
  const results: string[] = [];
  
  const canForm = (word: string, isOriginal: boolean): boolean => {
    if (memo.has(word)) return memo.get(word)!;
    
    if (!isOriginal && wordSet.has(word)) {
      memo.set(word, true);
      return true;
    }
    
    for (let i = 1; i < word.length; i++) {
      const prefix = word.substring(0, i);
      const suffix = word.substring(i);
      
      if (wordSet.has(prefix) && canForm(suffix, false)) {
        memo.set(word, true);
        return true;
      }
    }
    
    memo.set(word, false);
    return false;
  };
  
  for (const word of words) {
    if (canForm(word, true)) {
      results.push(word);
    }
  }
  
  return results;
}

Pattern 5: Word Break Count

Count number of ways to break string.

function wordBreakCount(s: string, wordDict: string[]): number {
  const wordSet = new Set(wordDict);
  const n = s.length;
  const dp: number[] = new Array(n + 1).fill(0);
  dp[0] = 1; // One way to break empty string
  
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] > 0 && wordSet.has(s.substring(j, i))) {
        dp[i] += dp[j];
      }
    }
  }
  
  return dp[n];
}

Time: O(n^2), Space: O(n)

Pattern 6: Word Break with Minimum Cost

Find minimum cost word break.

function wordBreakMinCost(s: string, wordDict: string[], costs: Map<string, number>): number {
  const wordSet = new Set(wordDict);
  const n = s.length;
  const dp: number[] = new Array(n + 1).fill(Infinity);
  dp[0] = 0;
  
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      const word = s.substring(j, i);
      if (wordSet.has(word) && dp[j] !== Infinity) {
        const cost = costs.get(word) || 0;
        dp[i] = Math.min(dp[i], dp[j] + cost);
      }
    }
  }
  
  return dp[n] === Infinity ? -1 : dp[n];
}

Time: O(n^2), Space: O(n)

Pattern 7: Word Break with Constraints

Word break with additional constraints.

Maximum word length:

function wordBreakWithMaxLength(s: string, wordDict: string[], maxLength: number): boolean {
  const wordSet = new Set(wordDict.filter(w => w.length <= maxLength));
  const n = s.length;
  const dp: boolean[] = new Array(n + 1).fill(false);
  dp[0] = true;
  
  for (let i = 1; i <= n; i++) {
    for (let j = Math.max(0, i - maxLength); j < i; j++) {
      if (dp[j] && wordSet.has(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  
  return dp[n];
}

Minimum word count:

function wordBreakMinWords(s: string, wordDict: string[], minWords: number): boolean {
  const wordSet = new Set(wordDict);
  const n = s.length;
  const dp: number[] = new Array(n + 1).fill(Infinity);
  dp[0] = 0;
  
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (wordSet.has(s.substring(j, i)) && dp[j] !== Infinity) {
        dp[i] = Math.min(dp[i], dp[j] + 1);
      }
    }
  }
  
  return dp[n] >= minWords;
}

Pattern 8: Word Break Path Reconstruction

Reconstruct the actual word break path.

function wordBreakPath(s: string, wordDict: string[]): string[] | null {
  const wordSet = new Set(wordDict);
  const n = s.length;
  const dp: boolean[] = new Array(n + 1).fill(false);
  const parent: number[] = new Array(n + 1).fill(-1);
  dp[0] = true;
  
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.substring(j, i))) {
        dp[i] = true;
        parent[i] = j;
        break;
      }
    }
  }
  
  if (!dp[n]) return null;
  
  // Reconstruct path
  const path: string[] = [];
  let i = n;
  
  while (i > 0) {
    const j = parent[i];
    path.unshift(s.substring(j, i));
    i = j;
  }
  
  return path;
}

Time: O(n^2), Space: O(n)

Pattern 9: Word Break with Wildcards

Handle word break with wildcard characters.

function wordBreakWildcard(s: string, wordDict: string[]): boolean {
  const wordSet = new Set(wordDict);
  const n = s.length;
  const dp: boolean[] = new Array(n + 1).fill(false);
  dp[0] = true;
  
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j]) {
        const subWord = s.substring(j, i);
        
        // Check exact match or wildcard match
        if (wordSet.has(subWord) || matchesWildcard(subWord, wordSet)) {
          dp[i] = true;
          break;
        }
      }
    }
  }
  
  return dp[n];
}

function matchesWildcard(word: string, wordSet: Set<string>): boolean {
  for (const dictWord of wordSet) {
    if (word.length === dictWord.length) {
      let match = true;
      for (let i = 0; i < word.length; i++) {
        if (word[i] !== '?' && word[i] !== dictWord[i]) {
          match = false;
          break;
        }
      }
      if (match) return true;
    }
  }
  return false;
}

Pattern 10: Word Break Optimization

Optimize word break for repeated queries.

class WordBreakOptimizer {
  private wordSet: Set<string>;
  private maxLen: number;
  private cache: Map<string, boolean>;
  
  constructor(wordDict: string[]) {
    this.wordSet = new Set(wordDict);
    this.maxLen = Math.max(...wordDict.map(w => w.length));
    this.cache = new Map();
  }
  
  canBreak(s: string): boolean {
    if (this.cache.has(s)) {
      return this.cache.get(s)!;
    }
    
    const n = s.length;
    const dp: boolean[] = new Array(n + 1).fill(false);
    dp[0] = true;
    
    for (let i = 1; i <= n; i++) {
      for (let j = Math.max(0, i - this.maxLen); j < i; j++) {
        if (dp[j] && this.wordSet.has(s.substring(j, i))) {
          dp[i] = true;
          break;
        }
      }
    }
    
    this.cache.set(s, dp[n]);
    return dp[n];
  }
  
  clearCache(): void {
    this.cache.clear();
  }
}

Pattern 11: Word Break with Trie Optimization

Use Trie for efficient prefix matching.

function wordBreakTrieOptimized(s: string, wordDict: string[]): boolean {
  const trie = new Trie(wordDict);
  const n = s.length;
  const dp: boolean[] = new Array(n + 1).fill(false);
  dp[0] = true;
  
  for (let i = 0; i < n; i++) {
    if (!dp[i]) continue;
    
    let node = trie.root;
    for (let j = i; j < n; j++) {
      const char = s[j];
      if (!node.children.has(char)) break;
      
      node = node.children.get(char)!;
      if (node.isEnd) {
        dp[j + 1] = true;
      }
    }
  }
  
  return dp[n];
}

Time: O(n^2), Space: O(n + m)

Pattern 12: Word Break All Combinations

Find all possible word break combinations.

function wordBreakAllCombinations(s: string, wordDict: string[]): string[][] {
  const wordSet = new Set(wordDict);
  const memo = new Map<number, string[][]>();
  
  const backtrack = (start: number): string[][] => {
    if (start === s.length) {
      return [[]];
    }
    
    if (memo.has(start)) {
      return memo.get(start)!;
    }
    
    const results: string[][] = [];
    
    for (let end = start + 1; end <= s.length; end++) {
      const word = s.substring(start, end);
      
      if (wordSet.has(word)) {
        const subCombinations = backtrack(end);
        
        for (const subCombo of subCombinations) {
          results.push([word, ...subCombo]);
        }
      }
    }
    
    memo.set(start, results);
    return results;
  };
  
  return backtrack(0);
}

Time: O(2^n), Space: O(2^n)

When to Use Word Break Techniques

Use word break algorithms when:

  • Problem mentions "word break", "segmentation", or "dictionary"
  • Need to check if segmentation is possible
  • Find all segmentations or combinations
  • Optimize repeated queries
  • Handle constraints on word breaks
  • Concatenated words problems

Template (DP-based)

function wordBreakTemplate(s: string, wordDict: string[]): boolean {
  const wordSet = new Set(wordDict);
  const n = s.length;
  const dp: boolean[] = new Array(n + 1).fill(false);
  dp[0] = true;
  
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  
  return dp[n];
}

Template (Backtracking with Memo)

function wordBreakBacktrackTemplate(s: string, wordDict: string[]): string[] {
  const wordSet = new Set(wordDict);
  const memo = new Map<number, string[]>();
  
  const backtrack = (start: number): string[] => {
    if (start === s.length) return [''];
    if (memo.has(start)) return memo.get(start)!;
    
    const results: string[] = [];
    
    for (let end = start + 1; end <= s.length; end++) {
      const word = s.substring(start, end);
      if (wordSet.has(word)) {
        const subResults = backtrack(end);
        for (const sub of subResults) {
          results.push(sub === '' ? word : word + ' ' + sub);
        }
      }
    }
    
    memo.set(start, results);
    return results;
  };
  
  return backtrack(0);
}

Time and Space Complexity Summary

  • Basic word break: O(n^2) time, O(n) space
  • Word break II: O(2^n) time, O(2^n) space
  • With Trie: O(n^2) time, O(n + m) space
  • Concatenated words: O(n * m^2) time, O(m) space
  • Word break count: O(n^2) time, O(n) space
  • All combinations: O(2^n) time, O(2^n) space

Practice Tips

  1. Use DP — For checking if break is possible
  2. Use backtracking — For finding all combinations
  3. Memoization — Essential for optimization
  4. Trie optimization — For efficient prefix matching
  5. Early termination — Check feasibility first
  6. Handle edge cases — Empty string, empty dict

Common Mistakes

  1. Not memoizing — Causes TLE in backtracking
  2. Wrong DP state — dp[i] should represent breakable up to i
  3. Index errors — Careful with substring indices
  4. Not checking empty string — dp[0] = true
  5. Inefficient matching — Use Trie or Set for lookup

Related Concepts

  • Dynamic Programming — Core technique for word break
  • Backtracking — For finding all solutions
  • Trie — For efficient word matching
  • String Matching — Pattern matching in strings

Word break problems are common in interviews. Master these patterns, and you'll be well-prepared for segmentation and dictionary-related questions.

← PreviousValid Parentheses/StringNext →String Interleaving