StringProblem 43 of 43
Recursively print all sentences that can be formed from list of word lists
Problem Statement
Given a list of word lists, recursively print all possible sentences that can be formed by picking one word from each list.
Example:
- Input:
[ ["you", "we"], ["have", "are"], ["sleep", "eat", "drink"] ] - Output:
"you have sleep" "you have eat" "you have drink" "you are sleep" "you are eat" "you are drink" "we have sleep" "we have eat" "we have drink" "we are sleep" "we are eat" "we are drink"
Approach 1: Brute Force (Nested Loops)
Intuition
For a fixed number of word lists, use nested loops. This doesn't scale for arbitrary number of lists.
This is impractical for variable number of lists.
Approach 2: Recursion (Backtracking)
Intuition
Use recursion to handle arbitrary number of word lists. At each level, pick one word from the current list and recurse to the next list.
Algorithm
- Start with empty sentence and first word list
- For each word in current list:
- Add word to sentence
- Recurse to next list
- Remove word (backtrack)
- When all lists exhausted, print/store the sentence
java
import java.util.*;
public class Solution {
public List<String> getAllSentences(List<List<String>> wordLists) {
List<String> result = new ArrayList<>();
if (wordLists.isEmpty()) return result;
backtrack(wordLists, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(List<List<String>> wordLists, int index,
List<String> current, List<String> result) {
if (index == wordLists.size()) {
result.add(String.join(" ", current));
return;
}
for (String word : wordLists.get(index)) {
current.add(word);
backtrack(wordLists, index + 1, current, result);
current.remove(current.size() - 1);
}
}
}Complexity Analysis
- Time Complexity: O(L^n * n) where L is average words per list, n is number of lists
- Space Complexity: O(n) for recursion stack, O(L^n * n) for storing results
Approach 3: Iterative with Queue
Intuition
Use a queue to build sentences iteratively. Start with empty sentence, for each word list, expand all current partial sentences.
java
import java.util.*;
public class Solution {
public List<String> getAllSentences(List<List<String>> wordLists) {
if (wordLists.isEmpty()) return new ArrayList<>();
Queue<String> queue = new LinkedList<>();
queue.offer("");
for (List<String> wordList : wordLists) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String current = queue.poll();
for (String word : wordList) {
String newSentence = current.isEmpty() ? word : current + " " + word;
queue.offer(newSentence);
}
}
}
return new ArrayList<>(queue);
}
}Complexity Analysis
- Time Complexity: O(L^n * n)
- Space Complexity: O(L^n * n) for queue storage
Approach 4: Using Index Array (Iterative Simulation)
Intuition
Treat the problem like counting in a mixed-radix number system. Each word list is a "digit" with its own base.
java
import java.util.*;
public class Solution {
public List<String> getAllSentences(List<List<String>> wordLists) {
List<String> result = new ArrayList<>();
if (wordLists.isEmpty()) return result;
int n = wordLists.size();
int[] indices = new int[n];
while (true) {
StringBuilder sentence = new StringBuilder();
for (int i = 0; i < n; i++) {
if (i > 0) sentence.append(" ");
sentence.append(wordLists.get(i).get(indices[i]));
}
result.add(sentence.toString());
int pos = n - 1;
while (pos >= 0) {
indices[pos]++;
if (indices[pos] < wordLists.get(pos).size()) {
break;
}
indices[pos] = 0;
pos--;
}
if (pos < 0) break;
}
return result;
}
}Complexity Analysis
- Time Complexity: O(L^n * n)
- Space Complexity: O(n) for indices array (excluding output)
Dry Run Example
wordLists = [["you", "we"], ["have", "are"], ["sleep", "eat"]]
Iteration 1: indices = [0, 0, 0] → "you have sleep"
Iteration 2: indices = [0, 0, 1] → "you have eat"
Iteration 3: indices = [0, 1, 0] → "you are sleep"
Iteration 4: indices = [0, 1, 1] → "you are eat"
Iteration 5: indices = [1, 0, 0] → "we have sleep"
Iteration 6: indices = [1, 0, 1] → "we have eat"
Iteration 7: indices = [1, 1, 0] → "we are sleep"
Iteration 8: indices = [1, 1, 1] → "we are eat"
Iteration 9: indices would be [2, 0, 0] but 2 >= size, done
Output: 8 sentences
Key Takeaways
- Recursion with backtracking is the natural approach for this problem
- Iterative index simulation treats it as a counting problem
- Total sentences = product of sizes of all word lists
- All approaches have same time complexity - it's inherent to the problem
- This is a Cartesian product of multiple sets
- Related: Generate Parentheses, Letter Combinations of a Phone Number