Recursive String Partitioning — Problem Statement & Solution Guide
Problem Description
Given a continuous string s and a finite set of distinct dictionary words, identify all unique sequences of words from the dictionary that can be concatenated to exactly reconstruct s. The reconstruction must preserve the original character order of s and utilize every character exactly once without omission or duplication.
The input begins with the string s followed by a list of dictionary words. Your task is to return a list of all valid partitions. Each partition is represented as a list of words in the order they appear in the reconstruction. If no valid partition exists, return an empty list.
Note: The dictionary words are distinct, and the order of words in the output sequences must match their occurrence in s. Duplicate sequences (same words in same order) should not be included in the result.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Recursive String Partitioning"
WHY DOES IT MATTER?
This pattern is essential for solving problems involving sequence reconstruction, parsing, and combinatorial generation. It teaches the balance between exhaustive search and memoization, a critical skill for optimizing algorithms in real-world applications where input sizes can vary significantly.
OPTIMIZATION CHALLENGE
The key insight is to use memoization to store the results of subproblems. By caching the list of valid partitions for a given starting index, we avoid redundant computations. Additionally, using a Trie or a hash set for word lookup ensures that each word check is O(1) or O(L), respectively, rather than O(N) for a linear scan.
REAL-WORLD CONNECTION
This is analogous to parsing a URL or a file path into its components. For example, breaking down 'user/profile/settings' into 'user', 'profile', and 'settings' requires identifying valid segments from a known set of path components. Similarly, in network protocols, packets are parsed into headers and payloads based on predefined structures.
During the interview, start by discussing the naive approach and its exponential complexity. Then, introduce memoization as a way to reduce the time complexity to O(N^2) or O(N*L) depending on the lookup structure. Emphasize the importance of pruning invalid branches early to improve performance.
COMPLEXITY AT A GLANCE
O(N^2 * L)O(N^2)Core Theory — Why This Approach?
The problem of partitioning a string into dictionary words is a classic application of dynamic programming combined with backtracking. The core challenge lies in the exponential nature of the search space: for a string of length N, there are potentially 2^(N-1) ways to partition it. A naive recursive approach that explores every possible split without memoization will result in a Time Limit Exceeded (TLE) error for moderately sized inputs because it repeatedly solves the same subproblems. For instance, if the string is 'aaaa' and the dictionary contains 'a', 'aa', 'aaa', the subproblem starting at index 1 is solved multiple times across different branches of the recursion tree.
Interview Questions on This Problem
Q1At a fintech platform, we need to parse transaction logs into standardized event types. How would you design a system to efficiently map raw log strings to known event patterns while handling high-throughput data?
I would use a Trie (prefix tree) to store the known event patterns for O(L) lookup where L is the length of the pattern. Then, I would employ a recursive backtracking algorithm with memoization to find all valid partitions. To handle high throughput, I would parallelize the search for independent log entries and use a cache for frequently occurring substrings to avoid redundant computation.
Q2In a high-growth startup, our search engine needs to suggest autocomplete corrections. How can we ensure that the suggestions are generated quickly without consuming excessive memory?
I would implement a Trie to store the dictionary of valid words. For the partitioning logic, I would use DFS with memoization to find valid sequences. To manage memory, I would limit the depth of the recursion and prune branches early if the remaining substring length exceeds the maximum word length in the dictionary. Additionally, I would use a hash set for O(1) word existence checks if the dictionary is small.
Q3At a global product company, we are building a natural language processing pipeline. How would you handle the ambiguity of word segmentation in a language without spaces, such as Chinese?
This is a direct application of the word break problem. I would use a dynamic programming approach to determine if a segmentation is possible and then use backtracking to generate all possible segmentations. To handle ambiguity, I would integrate a language model to score the likelihood of each segmentation and return the top-k most probable results. This ensures that the most contextually relevant interpretations are prioritized.
Examples
Input
s = "catdog", dictionary = ["cat", "dog", "catdog"]
Output
[["cat", "dog"], ["catdog"]]
Explanation: 1. Start with the full string "catdog". 2. Check if "catdog" is in the dictionary: Yes. Add ["catdog"] to results. 3. Check if "cat" is in the dictionary: Yes. Recurse on the remaining substring "dog". 4. In the recursive call for "dog": Check if "dog" is in the dictionary: Yes. Add ["cat", "dog"] to results. 5. No other valid prefixes exist. Return both sequences.
Input
s = "aaaa", dictionary = ["a", "aa", "aaa"]
Output
[["a", "a", "a", "a"], ["a", "a", "aa"], ["a", "aa", "a"], ["aa", "a", "a"], ["aa", "aa"], ["aaa", "a"], ["a", "aaa"]]
Explanation: 1. Start with "aaaa". 2. Try prefix "a": Remaining "aaa". Recurse. - Try prefix "a": Remaining "aa". Recurse. - Try prefix "a": Remaining "a". Recurse. - Try prefix "a": Remaining "". Add ["a", "a", "a", "a"]. - Try prefix "aa": Remaining "". Add ["a", "a", "aa"]. - Try prefix "aa": Remaining "a". Recurse. - Try prefix "a": Remaining "". Add ["a", "aa", "a"]. - Try prefix "aaa": Remaining "". Add ["a", "aaa"]. 3. Try prefix "aa": Remaining "aa". Recurse. - Try prefix "a": Remaining "a". Recurse. - Try prefix "a": Remaining "". Add ["aa", "a", "a"]. - Try prefix "aa": Remaining "". Add ["aa", "aa"]. 4. Try prefix "aaa": Remaining "a". Recurse. - Try prefix "a": Remaining "". Add ["aaa", "a"]. 5. Return all 7 unique sequences.
Input
s = "abc", dictionary = ["ab", "c", "abc"]
Output
[["ab", "c"], ["abc"]]
Explanation: 1. Start with "abc". 2. Check if "abc" is in the dictionary: Yes. Add ["abc"] to results. 3. Check if "ab" is in the dictionary: Yes. Recurse on remaining "c". 4. In recursive call for "c": Check if "c" is in the dictionary: Yes. Add ["ab", "c"] to results. 5. No other valid prefixes. Return both sequences.
Input
s = "xyz", dictionary = ["xy", "z", "x"]
Output
[["xy", "z"]]
Explanation: 1. Start with "xyz". 2. Check if "xyz" is in the dictionary: No. 3. Check if "xy" is in the dictionary: Yes. Recurse on remaining "z". 4. In recursive call for "z": Check if "z" is in the dictionary: Yes. Add ["xy", "z"] to results. 5. Check if "x" is in the dictionary: Yes. Recurse on remaining "yz". 6. In recursive call for "yz": No prefix of "yz" is in the dictionary. Return empty. 7. Return only ["xy", "z"].
Constraints
- 1 <= s.length <= 20
- 1 <= dictionary.length <= 100
- 1 <= dictionary[i].length <= 20
- s and dictionary[i] consist of lowercase English letters
- All words in dictionary are distinct
Optimal Approach & Strategy
The optimized approach uses dynamic programming with memoization to store the results of subproblems. By caching the valid partitions for each starting index, we avoid redundant computations and reduce the time complexity to O(N^2) or O(N*L), where L is the average length of the words in the dictionary.
Brute Force Approach
The brute force approach involves recursively trying every possible split of the string and checking if each segment exists in the dictionary. This results in an exponential time complexity of O(2^N) because it explores all possible partitions without reusing previously computed results.
Verified Code Solutions
// Function to find all word break sequences
function wordBreak(s, dict) {
const wordSet = new Set(dict);
const memo = new Map();
function dfs(start) {
if (memo.has(start)) return memo.get(start);
const res = [];
if (start === s.length) return res.push([]), res;
for (let end = start + 1; end <= s.length; ++end) {
const sub = s.slice(start, end);
if (wordSet.has(sub)) {
const suffixes = dfs(end);
for (const seq of suffixes) {
res.push([sub, ...seq]);
}
}
}
memo.set(start, res);
return res;
}
return dfs(0);
}
const s = "catdog";
const dict = ["cat", "dog", "catdog"];
const result = wordBreak(s, dict);
result.forEach(seq => console.log(seq.join(' ')));#include <bits/stdc++.h>
using namespace std;
vector<vector<string>> wordBreak(const string& s, const vector<string>& dict) {
unordered_set<string> wordSet(dict.begin(), dict.end());
unordered_map<int, vector<vector<string>>> memo;
function<vector<vector<string>>(int)> dfs = [&](int start) {
if (memo.count(start)) return memo[start];
vector<vector<string>> res;
if (start == (int)s.size()) {
res.push_back({});
return memo[start] = res;
}
for (int end = start + 1; end <= (int)s.size(); ++end) {
string sub = s.substr(start, end - start);
if (wordSet.count(sub)) {
auto suffixes = dfs(end);
for (auto& seq : suffixes) {
vector<string> newSeq = {sub};
newSeq.insert(newSeq.end(), seq.begin(), seq.end());
res.push_back(newSeq);
}
}
}
return memo[start] = res;
};
return dfs(0);
}
int main() {
string s = "catdog";
vector<string> dict = {"cat", "dog", "catdog"};
auto result = wordBreak(s, dict);
for (const auto& seq : result) {
for (const auto& w : seq) cout << w << " ";
cout << endl;
}
return 0;
}
import java.util.*;
public class WordBreak {
public List<List<String>> wordBreak(String s, List<String> dictionary) {
Set<String> wordSet = new HashSet<>(dictionary);
Map<Integer, List<List<String>>> memo = new HashMap<>();
return dfs(s, 0, wordSet, memo);
}
private List<List<String>> dfs(String s, int start, Set<String> wordSet, Map<Integer, List<List<String>>> memo) {
if (memo.containsKey(start)) return memo.get(start);
List<List<String>> res = new ArrayList<>();
if (start == s.length()) {
res.add(new ArrayList<>());
return memo.put(start, res);
}
for (int end = start + 1; end <= s.length(); ++end) {
String sub = s.substring(start, end);
if (wordSet.contains(sub)) {
List<List<String>> suffixes = dfs(s, end, wordSet, memo);
for (List<String> seq : suffixes) {
List<String> newSeq = new ArrayList<>();
newSeq.add(sub);
newSeq.addAll(seq);
res.add(newSeq);
}
}
}
memo.put(start, res);
return res;
}
public static void main(String[] args) {
String s = "catdog";
List<String> dictionary = Arrays.asList("cat", "dog", "catdog");
WordBreak wb = new WordBreak();
List<List<String>> result = wb.wordBreak(s, dictionary);
for (List<String> seq : result) {
System.out.println(String.join(" ", seq));
}
}
}
# Function to find all word break sequences
def word_break(s, dictionary):
word_set = set(dictionary)
memo = {}
def dfs(start):
if start in memo:
return memo[start]
res = []
if start == len(s):
return [[]]
for end in range(start + 1, len(s) + 1):
sub = s[start:end]
if sub in word_set:
for seq in dfs(end):
res.append([sub] + seq)
memo[start] = res
return res
return dfs(0)
s = "catdog"
dictionary = ["cat", "dog", "catdog"]
result = word_break(s, dictionary)
for seq in result:
print(' '.join(seq))
// Function to find all word break sequences
function wordBreak(s, dict) {
const wordSet = new Set(dict);
const memo = new Map();
function dfs(start) {
if (memo.has(start)) return memo.get(start);
const res = [];
if (start === s.length) return res.push([]), res;
for (let end = start + 1; end <= s.length; ++end) {
const sub = s.slice(start, end);
if (wordSet.has(sub)) {
const suffixes = dfs(end);
for (const seq of suffixes) {
res.push([sub, ...seq]);
}
}
}
memo.set(start, res);
return res;
}
return dfs(0);
}
const s = "catdog";
const dict = ["cat", "dog", "catdog"];
const result = wordBreak(s, dict);
result.forEach(seq => console.log(seq.join(' ')));
Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.