Word Break II (All Sentences)

🎯

Word Break II (All Sentences)

hardDPAmazonFacebookGoogle

Imagine you are building a text auto-correct or auto-suggestion feature that needs to find all possible valid sentences from a string without spaces, using a dictionary of known words.

💡 This problem is a classic example of combining dynamic programming with backtracking. Beginners often struggle because it requires understanding how to efficiently explore all valid segmentations without redundant computations.

📋

Problem Statement

Given a string s and a dictionary of strings wordDict, return all possible sentences where s can be segmented into a space-separated sequence of one or more dictionary words. You may reuse dictionary words any number of times. Return the sentences in any order.

1 ≤ s.length ≤ 201 ≤ wordDict.length ≤ 10001 ≤ wordDict[i].length ≤ 10s and wordDict[i] consist of only lowercase English letters

💡

Example

Input"s = \"catsanddog\", wordDict = [\"cat\", \"cats\", \"and\", \"sand\", \"dog\"]"

Output["cats and dog", "cat sand dog"]

The string can be segmented as "cats and dog" or "cat sand dog" using the dictionary words.

Input"s = \"pineapplepenapple\", wordDict = [\"apple\", \"pen\", \"applepen\", \"pine\", \"pineapple\"]"

Output["pine apple pen apple", "pineapple pen apple", "pine applepen apple"]

Multiple segmentations are possible using overlapping dictionary words.

• Empty string s → returns empty list or list with empty string depending on interpretation
• String s with no valid segmentation → returns empty list
• Dictionary contains words that are substrings of others → all valid segmentations must be found
• String s equals a dictionary word → returns list with that word only

🔁

Why DP?

Why greedy fails:

A greedy approach might pick the longest matching word first, but this can miss valid segmentations. For example, with s='catsanddog' and dictionary containing 'cats' and 'cat', greedy picking 'cats' first works, but if 'cat' leads to more segmentations, greedy fails to find all.

DP state:

dp[i] stores all possible sentences that can be formed from the substring s[i:] using the dictionary words.

Recurrence:dp[i] = [word + (" " + sentence) for each word in wordDict if s[i:].startsWith(word) and sentence in dp[i + len(word)]]

For each position i, find dictionary words that match the substring starting at i, then append those words to all sentences formed from the remaining substring.

⚠️

Common Mistakes

Not caching results leading to TLE

Code times out on larger inputs due to exponential recursion

✅ Add memoization to cache results for substring indices

Incorrect string concatenation causing extra spaces

Output sentences have trailing or leading spaces

✅ Only add space when suffix sentence is non-empty

Using list instead of set for dictionary lookup

Membership checks become O(n), slowing down solution

✅ Convert wordDict to a set for O(1) lookups

Not handling base case correctly (empty string)

Recursion never terminates or returns incorrect results

✅ Return list with empty string when start == len(s)

Forgetting to check substring bounds before substring operations

Runtime errors or incorrect matches

✅ Check that substring indices are within string length before slicing

🧠

Brute Force (Pure Recursion)

💡 This approach is the foundation for understanding the problem. It tries all possible segmentations without caching, which is simple but inefficient.

Intuition

Try every prefix of the string; if it is a dictionary word, recursively solve for the remaining suffix and combine results.

Algorithm

1. Check every prefix of the current substring.
2. If prefix is in dictionary, recursively solve for the suffix.
3. Combine prefix with all sentences returned from suffix recursion.
4. Return all combined sentences.

💡 The recursion tree grows exponentially because it explores all segmentations without remembering previous results.

Recurrence:dp[i] = ∪ { word + ' ' + dp[i + len(word)] | word ∈ wordDict and s[i:].startsWith(word) }

</>

Code

from typing import List

def wordBreak(s: str, wordDict: List[str]) -> List[str]:
    word_set = set(wordDict)
    def backtrack(start):
        if start == len(s):
            return [""]
        res = []
        for end in range(start + 1, len(s) + 1):
            prefix = s[start:end]
            if prefix in word_set:
                suffix_ways = backtrack(end)
                for sentence in suffix_ways:
                    if sentence:
                        res.append(prefix + " " + sentence)
                    else:
                        res.append(prefix)
        return res

    return backtrack(0)

# Driver code
if __name__ == "__main__":
    s = "catsanddog"
    wordDict = ["cat", "cats", "and", "sand", "dog"]
    print(wordBreak(s, wordDict))

Line Notes

word_set = set(wordDict)Convert list to set for O(1) membership checks

def backtrack(start):Define recursive helper to find sentences starting at index start

if start == len(s):Base case: reached end of string, return list with empty string

for end in range(start + 1, len(s) + 1):Try every possible prefix from start to end

if prefix in word_set:Check if current prefix is a valid dictionary word

suffix_ways = backtrack(end)Recursively find sentences for the suffix starting at end

for sentence in suffix_ways:Combine current prefix with each suffix sentence

return resReturn all valid sentences starting at index start

import java.util.*;

public class WordBreakII {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        return backtrack(s, 0, wordSet);
    }

    private List<String> backtrack(String s, int start, Set<String> wordSet) {
        if (start == s.length()) {
            return Arrays.asList("");
        }
        List<String> res = new ArrayList<>();
        for (int end = start + 1; end <= s.length(); end++) {
            String prefix = s.substring(start, end);
            if (wordSet.contains(prefix)) {
                List<String> suffixWays = backtrack(s, end, wordSet);
                for (String sentence : suffixWays) {
                    if (sentence.isEmpty()) {
                        res.add(prefix);
                    } else {
                        res.add(prefix + " " + sentence);
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        WordBreakII solver = new WordBreakII();
        String s = "catsanddog";
        List<String> wordDict = Arrays.asList("cat", "cats", "and", "sand", "dog");
        System.out.println(solver.wordBreak(s, wordDict));
    }
}

Line Notes

Set<String> wordSet = new HashSet<>(wordDict);Use HashSet for fast word lookup

if (start == s.length()) {Base case: reached end of string, return list with empty string

for (int end = start + 1; end <= s.length(); end++) {Try every prefix from start to end

if (wordSet.contains(prefix)) {Check if prefix is a dictionary word

List<String> suffixWays = backtrack(s, end, wordSet);Recursively get sentences for suffix

for (String sentence : suffixWays) {Combine prefix with each suffix sentence

res.add(prefix + " " + sentence);Add combined sentence to results

return res;Return all sentences starting at start

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

using namespace std;

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        return backtrack(s, 0, wordSet);
    }

private:
    vector<string> backtrack(const string& s, int start, const unordered_set<string>& wordSet) {
        if (start == s.size()) {
            return {""};
        }
        vector<string> res;
        for (int end = start + 1; end <= (int)s.size(); ++end) {
            string prefix = s.substr(start, end - start);
            if (wordSet.count(prefix)) {
                vector<string> suffixWays = backtrack(s, end, wordSet);
                for (const string& sentence : suffixWays) {
                    if (sentence.empty()) {
                        res.push_back(prefix);
                    } else {
                        res.push_back(prefix + " " + sentence);
                    }
                }
            }
        }
        return res;
    }
};

int main() {
    Solution sol;
    string s = "catsanddog";
    vector<string> wordDict = {"cat", "cats", "and", "sand", "dog"};
    vector<string> result = sol.wordBreak(s, wordDict);
    for (const string& sentence : result) {
        cout << sentence << endl;
    }
    return 0;
}

Line Notes

unordered_set<string> wordSet(wordDict.begin(), wordDict.end());Create hash set for O(1) word lookup

if (start == s.size()) {Base case: reached end of string, return vector with empty string

for (int end = start + 1; end <= (int)s.size(); ++end) {Try every prefix from start to end

if (wordSet.count(prefix)) {Check if prefix is in dictionary

vector<string> suffixWays = backtrack(s, end, wordSet);Recursively get sentences for suffix

for (const string& sentence : suffixWays) {Combine prefix with each suffix sentence

res.push_back(prefix + " " + sentence);Add combined sentence to results

return res;Return all sentences starting at start

function wordBreak(s, wordDict) {
    const wordSet = new Set(wordDict);
    function backtrack(start) {
        if (start === s.length) return [""];
        const res = [];
        for (let end = start + 1; end <= s.length; end++) {
            const prefix = s.substring(start, end);
            if (wordSet.has(prefix)) {
                const suffixWays = backtrack(end);
                for (const sentence of suffixWays) {
                    res.push(sentence ? prefix + " " + sentence : prefix);
                }
            }
        }
        return res;
    }
    return backtrack(0);
}

// Test
console.log(wordBreak("catsanddog", ["cat", "cats", "and", "sand", "dog"]));

Line Notes

const wordSet = new Set(wordDict);Use Set for O(1) word membership checks

function backtrack(start) {Recursive helper to find sentences starting at index start

if (start === s.length) return [""];Base case: reached end of string, return list with empty string

for (let end = start + 1; end <= s.length; end++) {Try every prefix from start to end

if (wordSet.has(prefix)) {Check if prefix is a dictionary word

const suffixWays = backtrack(end);Recursively get sentences for suffix

res.push(sentence ? prefix + " " + sentence : prefix);Combine prefix with suffix sentences

return res;Return all sentences starting at start

⏱

Complexity

TimeO(2^n * n) due to exploring all segmentations and string concatenations

SpaceO(n^2) for recursion stack and storing intermediate strings

The recursion explores all possible segmentations, which can be exponential in number. Each concatenation and substring operation adds linear overhead.

💡 For n=20, this could mean millions of recursive calls, making it impractical for large inputs.

Interview Verdict: TLE / Use only to introduce problem and motivate memoization

This approach is too slow for large inputs but is essential to understand before optimizing.

🧠

Top-Down Memoization (Recursion + Cache)

💡 Memoization avoids recomputing results for the same substring, drastically improving efficiency while keeping the recursive structure.

Intuition

Cache the results of recursive calls so that each substring is solved once, then reused whenever needed.

Algorithm

1. Initialize a cache (dictionary) to store results for substring indices.
2. Recursively try every prefix; if prefix is in dictionary, recurse on suffix.
3. Before recursion, check if result for suffix is cached; if yes, reuse it.
4. Combine prefix with cached suffix sentences and store in cache.
5. Return cached results for each substring.

💡 Memoization transforms exponential recursion into polynomial time by reusing results.

Recurrence:dp[i] = ∪ { word + ' ' + dp[i + len(word)] | word ∈ wordDict and s[i:].startsWith(word) } with memoization

</>

Code

from typing import List

def wordBreak(s: str, wordDict: List[str]) -> List[str]:
    word_set = set(wordDict)
    memo = {}

    def backtrack(start):
        if start in memo:
            return memo[start]
        if start == len(s):
            return [""]
        res = []
        for end in range(start + 1, len(s) + 1):
            prefix = s[start:end]
            if prefix in word_set:
                suffix_ways = backtrack(end)
                for sentence in suffix_ways:
                    res.append(prefix + (" " + sentence if sentence else ""))
        memo[start] = res
        return res

    return backtrack(0)

# Driver code
if __name__ == "__main__":
    s = "catsanddog"
    wordDict = ["cat", "cats", "and", "sand", "dog"]
    print(wordBreak(s, wordDict))

Line Notes

memo = {}Initialize cache to store results for substring indices

if start in memo:Return cached result if available to avoid recomputation

memo[start] = resStore computed results in cache before returning

res.append(prefix + (" " + sentence if sentence else ""))Concatenate prefix with suffix sentences carefully to avoid trailing spaces

import java.util.*;

public class WordBreakII {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        Map<Integer, List<String>> memo = new HashMap<>();
        return backtrack(s, 0, wordSet, memo);
    }

    private List<String> backtrack(String s, int start, Set<String> wordSet, Map<Integer, List<String>> memo) {
        if (memo.containsKey(start)) {
            return memo.get(start);
        }
        if (start == s.length()) {
            return Arrays.asList("");
        }
        List<String> res = new ArrayList<>();
        for (int end = start + 1; end <= s.length(); end++) {
            String prefix = s.substring(start, end);
            if (wordSet.contains(prefix)) {
                List<String> suffixWays = backtrack(s, end, wordSet, memo);
                for (String sentence : suffixWays) {
                    res.add(prefix + (sentence.isEmpty() ? "" : " " + sentence));
                }
            }
        }
        memo.put(start, res);
        return res;
    }

    public static void main(String[] args) {
        WordBreakII solver = new WordBreakII();
        String s = "catsanddog";
        List<String> wordDict = Arrays.asList("cat", "cats", "and", "sand", "dog");
        System.out.println(solver.wordBreak(s, wordDict));
    }
}

Line Notes

Map<Integer, List<String>> memo = new HashMap<>();Cache results for substring start indices

if (memo.containsKey(start)) {Return cached results if available

memo.put(start, res);Store computed results before returning

res.add(prefix + (sentence.isEmpty() ? "" : " " + sentence));Concatenate prefix and suffix sentences carefully

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        unordered_map<int, vector<string>> memo;
        return backtrack(s, 0, wordSet, memo);
    }

private:
    vector<string> backtrack(const string& s, int start, const unordered_set<string>& wordSet, unordered_map<int, vector<string>>& memo) {
        if (memo.count(start)) {
            return memo[start];
        }
        if (start == (int)s.size()) {
            return {""};
        }
        vector<string> res;
        for (int end = start + 1; end <= (int)s.size(); ++end) {
            string prefix = s.substr(start, end - start);
            if (wordSet.count(prefix)) {
                vector<string> suffixWays = backtrack(s, end, wordSet, memo);
                for (const string& sentence : suffixWays) {
                    res.push_back(prefix + (sentence.empty() ? "" : " " + sentence));
                }
            }
        }
        memo[start] = res;
        return res;
    }
};

int main() {
    Solution sol;
    string s = "catsanddog";
    vector<string> wordDict = {"cat", "cats", "and", "sand", "dog"};
    vector<string> result = sol.wordBreak(s, wordDict);
    for (const string& sentence : result) {
        cout << sentence << endl;
    }
    return 0;
}

Line Notes

unordered_map<int, vector<string>> memo;Cache results for substring start indices

if (memo.count(start)) {Return cached results if available

memo[start] = res;Store computed results before returning

res.push_back(prefix + (sentence.empty() ? "" : " " + sentence));Concatenate prefix and suffix sentences carefully

function wordBreak(s, wordDict) {
    const wordSet = new Set(wordDict);
    const memo = new Map();

    function backtrack(start) {
        if (memo.has(start)) return memo.get(start);
        if (start === s.length) return [""];
        const res = [];
        for (let end = start + 1; end <= s.length; end++) {
            const prefix = s.substring(start, end);
            if (wordSet.has(prefix)) {
                const suffixWays = backtrack(end);
                for (const sentence of suffixWays) {
                    res.push(sentence ? prefix + " " + sentence : prefix);
                }
            }
        }
        memo.set(start, res);
        return res;
    }

    return backtrack(0);
}

// Test
console.log(wordBreak("catsanddog", ["cat", "cats", "and", "sand", "dog"]));

Line Notes

const memo = new Map();Cache results for substring start indices

if (memo.has(start)) return memo.get(start);Return cached results if available

memo.set(start, res);Store computed results before returning

res.push(sentence ? prefix + " " + sentence : prefix);Concatenate prefix and suffix sentences carefully

⏱

Complexity

TimeO(n^3) in worst case due to memoization and string concatenations

SpaceO(n^3) for memo storage and recursion stack

Memoization ensures each substring is solved once, but concatenations and list merges add cubic overhead.

💡 For n=20, this approach is efficient enough to run comfortably within time limits.

Interview Verdict: Accepted / Efficient for interview coding

This is the recommended approach to implement in interviews for this problem.

🧠

Bottom-Up Tabulation with Backtracking

💡 This approach builds solutions from the end of the string upwards, storing all possible sentences for each substring, avoiding recursion overhead.

Intuition

Start from the end of the string and iteratively build all sentences for each substring by appending dictionary words that match the prefix.

Algorithm

1. Initialize dp array of size n+1 with dp[n] = [''] as base case.
2. Iterate i from n-1 down to 0.
3. For each i, check all dictionary words that match s starting at i.
4. For each matching word, append it to sentences in dp[i + len(word)] and add to dp[i].
5. Return dp[0] as all sentences for the entire string.

💡 This bottom-up approach avoids recursion and uses a table to store partial results, making it easier to understand and debug.

Recurrence:dp[i] = ∪ { word + ' ' + dp[i + len(word)] | word ∈ wordDict and s[i:].startsWith(word) }

</>

Code

from typing import List

def wordBreak(s: str, wordDict: List[str]) -> List[str]:
    word_set = set(wordDict)
    n = len(s)
    dp = [[] for _ in range(n + 1)]
    dp[n] = [""]

    for i in range(n - 1, -1, -1):
        sentences = []
        for word in word_set:
            if s.startswith(word, i):
                for sentence in dp[i + len(word)]:
                    sentences.append(word + (" " + sentence if sentence else ""))
        dp[i] = sentences

    return dp[0]

# Driver code
if __name__ == "__main__":
    s = "catsanddog"
    wordDict = ["cat", "cats", "and", "sand", "dog"]
    print(wordBreak(s, wordDict))

Line Notes

dp = [[] for _ in range(n + 1)]Initialize dp array with empty lists for each substring start

dp[n] = [""]Base case: empty string has one valid sentence (empty)

for i in range(n - 1, -1, -1):Fill dp from end to start to ensure suffix results are ready

if s.startswith(word, i):Check if dictionary word matches substring starting at i

for sentence in dp[i + len(word)]:Combine current word with all suffix sentences

sentences.append(word + (" " + sentence if sentence else ""))Build full sentences carefully avoiding trailing spaces

dp[i] = sentencesStore all sentences starting at index i

import java.util.*;

public class WordBreakII {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        int n = s.length();
        List<List<String>> dp = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            dp.add(new ArrayList<>());
        }
        dp.get(n).add("");

        for (int i = n - 1; i >= 0; i--) {
            List<String> sentences = new ArrayList<>();
            for (String word : wordSet) {
                if (i + word.length() <= n && s.startsWith(word, i)) {
                    for (String sentence : dp.get(i + word.length())) {
                        sentences.add(word + (sentence.isEmpty() ? "" : " " + sentence));
                    }
                }
            }
            dp.set(i, sentences);
        }

        return dp.get(0);
    }

    public static void main(String[] args) {
        WordBreakII solver = new WordBreakII();
        String s = "catsanddog";
        List<String> wordDict = Arrays.asList("cat", "cats", "and", "sand", "dog");
        System.out.println(solver.wordBreak(s, wordDict));
    }
}

Line Notes

List<List<String>> dp = new ArrayList<>();Create dp list of lists to store sentences for each index

dp.get(n).add("");Base case: empty string has one valid sentence

for (int i = n - 1; i >= 0; i--) {Fill dp from end to start

if (i + word.length() <= n && s.startsWith(word, i)) {Check if word matches substring starting at i

for (String sentence : dp.get(i + word.length())) {Combine word with suffix sentences

sentences.add(word + (sentence.isEmpty() ? "" : " " + sentence));Build full sentences carefully

dp.set(i, sentences);Store sentences starting at i

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

using namespace std;

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        int n = s.size();
        vector<vector<string>> dp(n + 1);
        dp[n].push_back("");

        for (int i = n - 1; i >= 0; --i) {
            vector<string> sentences;
            for (const string& word : wordSet) {
                if (i + (int)word.size() <= n && s.compare(i, word.size(), word) == 0) {
                    for (const string& sentence : dp[i + word.size()]) {
                        sentences.push_back(word + (sentence.empty() ? "" : " " + sentence));
                    }
                }
            }
            dp[i] = sentences;
        }

        return dp[0];
    }
};

int main() {
    Solution sol;
    string s = "catsanddog";
    vector<string> wordDict = {"cat", "cats", "and", "sand", "dog"};
    vector<string> result = sol.wordBreak(s, wordDict);
    for (const string& sentence : result) {
        cout << sentence << endl;
    }
    return 0;
}

Line Notes

vector<vector<string>> dp(n + 1);Create dp vector of vectors to store sentences for each index

dp[n].push_back("");Base case: empty string has one valid sentence

for (int i = n - 1; i >= 0; --i) {Fill dp from end to start

if (i + (int)word.size() <= n && s.compare(i, word.size(), word) == 0) {Check if word matches substring starting at i

for (const string& sentence : dp[i + word.size()]) {Combine word with suffix sentences

sentences.push_back(word + (sentence.empty() ? "" : " " + sentence));Build full sentences carefully

dp[i] = sentences;Store sentences starting at i

function wordBreak(s, wordDict) {
    const wordSet = new Set(wordDict);
    const n = s.length;
    const dp = Array(n + 1).fill(null).map(() => []);
    dp[n] = [""];

    for (let i = n - 1; i >= 0; i--) {
        const sentences = [];
        for (const word of wordSet) {
            if (s.startsWith(word, i)) {
                for (const sentence of dp[i + word.length]) {
                    sentences.push(sentence ? word + " " + sentence : word);
                }
            }
        }
        dp[i] = sentences;
    }

    return dp[0];
}

// Test
console.log(wordBreak("catsanddog", ["cat", "cats", "and", "sand", "dog"]));

Line Notes

const dp = Array(n + 1).fill(null).map(() => []);Initialize dp array with empty arrays for each index

dp[n] = [""];Base case: empty string has one valid sentence

for (let i = n - 1; i >= 0; i--) {Fill dp from end to start

if (s.startsWith(word, i)) {Check if word matches substring starting at i

for (const sentence of dp[i + word.length]) {Combine word with suffix sentences

sentences.push(sentence ? word + " " + sentence : word);Build full sentences carefully

dp[i] = sentences;Store sentences starting at i

⏱

Complexity

TimeO(n^3) due to nested loops and string concatenations

SpaceO(n^3) for dp storage and result lists

Each dp[i] can store multiple sentences, and checking all dictionary words adds overhead.

💡 This approach is efficient and avoids recursion stack overhead, suitable for interview coding.

Interview Verdict: Accepted / Optimal iterative DP solution

This approach is a great alternative to memoized recursion and shows strong DP skills.

📊

All Approaches - One-Glance Tradeoffs

💡 Memoized recursion is the best balance of simplicity and efficiency for interviews; tabulation is a strong alternative if you prefer iterative DP.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n * n)	O(n^2)	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down Memoization	O(n^3)	O(n^3)	Low (due to memoization)	Yes	Code this in 95% of interviews
3. Bottom-Up Tabulation	O(n^3)	O(n^3)	No	Yes	Good alternative if comfortable with iterative DP

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and examples.Explain brute force recursion and its exponential complexity.Introduce memoization to optimize repeated subproblems.Discuss bottom-up tabulation as an iterative alternative.Write clean code and test with edge cases.

Time Allocation

Clarify: 2min → Brute Force: 5min → Memoization: 8min → Tabulation: 8min → Testing: 5min. Total ~28min

What the Interviewer Tests

Understanding of recursion, memoization, DP state definition, and ability to optimize naive solutions.

Common Follow-ups

• What if dictionary is very large? → Use Trie or prefix pruning.
• Can you optimize space? → Use memoization only, no tabulation needed.
• How to handle duplicates in output? → Use sets or careful concatenation.
• What if you only need to check if segmentation is possible? → Use Word Break I DP.

💡 These follow-ups test your ability to adapt the solution to constraints and variants.

🔍

Pattern Recognition

When to Use

1) Asked to find all segmentations or decompositions of a string; 2) Given a dictionary of words; 3) Need to return all valid sentences; 4) Overlapping subproblems exist.

Signature Phrases

all possible sentencessegment string into dictionary wordsreturn all valid sentences

NOT This Pattern When

Problems asking only for count of segmentations or existence of segmentation without listing all solutions.

Similar Problems

Word Break I - decision problem variantPalindrome Partitioning - similar backtracking with DPRestore IP Addresses - segmentation with backtracking

Practice

1. You are given two strings and want to find the length of the longest substring that appears in both strings contiguously. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Longest Common Subsequence DP approach that allows skipping characters

B. Greedy approach that extends matching characters until a mismatch occurs

C. Dynamic Programming that builds a 2D table tracking lengths of matching suffixes

D. Sorting all substrings of both strings and finding the longest common prefix

Solution

1. Step 1: Understand problem requires contiguous matching substrings

   Longest Common Substring requires contiguous characters, so subsequence approaches that allow gaps won't work.

2. Step 2: Identify DP approach tracking matching suffix lengths

   Dynamic Programming with a 2D table (or optimized 1D) that stores lengths of matching suffixes at each index pair guarantees optimal solution.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only DP tracking contiguous matches solves this optimally [OK]

Hint: Longest common substring requires contiguous DP, not subsequence [OK]

Common Mistakes:

• Confusing substring with subsequence
• Trying greedy extension only
• Sorting substrings is inefficient

2. What is the time complexity of the space-optimized bottom-up DP solution for the longest common substring problem, where n and m are the lengths of the two input strings?

medium

A. O(n * m) due to nested loops comparing all character pairs

B. O(n * m) but with additional O(n + m) recursion stack space

C. O(n * m * min(n, m)) due to checking all substrings explicitly

D. O(n + m) due to single pass over both strings

Solution

1. Step 1: Identify nested loops over n and m

   The algorithm uses two nested loops: outer over n and inner over m, leading to O(n*m) iterations.

2. Step 2: Confirm no recursion or substring extraction

   Space optimization uses iterative DP with O(m) space, no recursion stack or substring extraction, so no extra multiplicative factors.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Nested loops over both strings dominate time complexity [OK]

Hint: Nested loops over both strings imply O(n*m) time [OK]

Common Mistakes:

• Confusing with linear O(n+m)
• Assuming recursion adds stack space
• Thinking substring extraction adds extra factor

3. The following code attempts to implement the space-optimized DP for longest common substring. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def longest_common_substring_space_optimized_buggy(s1, s2):
    n, m = len(s1), len(s2)
    dp = [0] * (m + 1)
    max_len = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):  # Note: iterating forward
            if s1[i - 1] == s2[j - 1]:
                dp[j] = dp[j - 1] + 1
                if dp[j] > max_len:
                    max_len = dp[j]
            else:
                dp[j] = 0
    return max_len

medium

A. Line with 'dp[j] = dp[j - 1] + 1' updating dp

B. Line with 'dp = [0] * (m + 1)' initializing dp array

C. Line with 'if dp[j] > max_len:' updating max_len

D. Line with 'for j in range(1, m + 1):' iterating forward

Solution

1. Step 1: Understand dp array update dependency

   dp[j] depends on dp[j-1] from previous iteration of inner loop, so iterating forward overwrites dp[j-1] before use.

2. Step 2: Identify iteration order bug

   Iterating j forward causes dp[j-1] to be updated before dp[j], corrupting the chain of matching lengths.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Changing inner loop to iterate backward fixes the bug [OK]

Hint: DP update depends on previous dp[j-1], so iterate backward [OK]

Common Mistakes:

• Updating dp forward overwrites needed values
• Incorrect max_len update timing
• Wrong dp initialization size

4. Examine the following buggy code for shortest common supersequence length. Which line contains the subtle bug that causes incorrect results when one input string is empty?

medium

A. Line 7: Condition comparing str1[i-1] and str2[j-1]

B. Line 5: Initialization of curr with [i] + [0]*n

C. Line 10: Updating prev = curr

D. Line 3: Initialization of prev with zeros instead of range

Solution

1. Step 1: Check base case initialization of prev array

   Prev should be initialized as range(n+1) to represent base case when str1 is empty; zeros cause incorrect base lengths.

2. Step 2: Confirm other lines correctly implement DP transitions

   Lines initializing curr, comparing characters, and updating prev are correct.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Incorrect base initialization leads to wrong results when one string is empty [OK]

Hint: Base case initialization must reflect empty string lengths [OK]

Common Mistakes:

• Initializing dp arrays with zeros instead of incremental ranges
• Mixing up indices in conditions
• Forgetting to update prev array

5. Suppose you want to find the longest common substring between two strings, but now substrings can be formed by reusing characters multiple times (i.e., characters can be repeated any number of times). Which modification to the DP approach correctly handles this variant?

hard

A. Use the same DP but allow dp[j] to accumulate without resetting to zero on mismatch

B. Modify DP to allow transitions from dp[j] and dp[j-1] to handle reuse, iterating forward over j

C. Use a suffix automaton or suffix trie data structure instead of DP

D. Apply longest common subsequence DP since reuse allows gaps and repeats

Solution

1. Step 1: Understand reuse means characters can be matched multiple times

   Longest common substring with reuse breaks contiguity and requires allowing repeated matches.

2. Step 2: Modify DP to allow reuse by iterating forward and allowing dp[j] to build on itself

   Iterating forward over j and allowing dp[j] to depend on dp[j] and dp[j-1] enables reuse of characters multiple times.

3. Step 3: Recognize other options fail

   Resetting dp on mismatch breaks reuse, suffix automaton is complex but not DP, subsequence DP allows gaps but not reuse as described.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Forward iteration with reuse transitions correctly models repeated characters [OK]

Hint: Reuse requires forward iteration and dp[j] depending on itself [OK]

Common Mistakes:

• Not resetting dp breaks reuse
• Using subsequence DP incorrectly
• Ignoring iteration order for reuse