Recursively print all sentences that can be formed from list of word lists

The problem, simply

You get n lists of words. A sentence takes exactly one word from list 0, then one from list 1, and so on, in that order. Print every sentence that can be made.

If the lists have sizes 2, 2 and 3, there are 2 * 2 * 3 = 12 sentences. Below, P is that product, the number of sentences.

A story to remember it

Picture it

Examples

Way 1: the simple way

Build the sentences one list at a time, like filling a tray. Start with one empty sentence. For each list, take every sentence you have so far and make a copy for each word of the list, with that word added at the end.

1. Put one empty sentence in a waiting line (a queue).
2. For each list, take out every sentence in the line and put back one longer sentence per word.
3. When all lists are used, the line holds every sentence.

import java.util.*;

class Solution {
    public List<String> sentences(List<List<String>> lists) {
        if (lists.isEmpty()) return new ArrayList<>();
        Queue<String> line = new ArrayDeque<>();
        line.add("");
        for (List<String> words : lists) {
            int size = line.size();
            for (int i = 0; i < size; i++) {
                String start = line.poll();
                for (String w : words) {
                    line.add(start.isEmpty() ? w : start + " " + w);   // one copy per word
                }
            }
        }
        return new ArrayList<>(line);
    }
}

How long it takes: every sentence is built word by word, O(P * n) letters of work if words are short. Extra room: the line holds every half built sentence of a level at once, and at the end all P full sentences, O(P * n), even if you only wanted to print them.

Way 2: the clever way

Walk the choice tree with recursion, the way your finger moves down the menu. Keep only the current path: one word per list chosen so far.

1. pick(i): if i equals the number of lists, the path is a full sentence. Print it.
2. Otherwise, for each word in list i: add it to the path, call pick(i + 1), then remove it.

The path never holds more than n words, so the memory stays tiny no matter how many sentences there are.

import java.util.*;

class Solution {
    public List<String> sentences(List<List<String>> lists) {
        List<String> out = new ArrayList<>();
        if (!lists.isEmpty()) pick(lists, 0, new ArrayList<>(), out);
        return out;
    }

    private void pick(List<List<String>> lists, int i, List<String> path, List<String> out) {
        if (i == lists.size()) {                  // one word from every list
            out.add(String.join(" ", path));      // or System.out.println(...)
            return;
        }
        for (String w : lists.get(i)) {
            path.add(w);                          // choose
            pick(lists, i + 1, path, out);        // go down one list
            path.remove(path.size() - 1);         // undo, try the next word
        }
    }
}

How long it takes: P sentences, each joined from n words, so O(P * n). No way can be faster, because that is the size of the output. Extra room: the path and the recursion are n deep, O(n), not counting the answers.

Watch out for

• An empty list anywhere means zero sentences. Both ways handle it: the loop over an empty list adds nothing.
• No lists at all is a special case. Decide with the interviewer whether that is zero sentences or one empty sentence.
• P grows fast: 10 lists of 5 words give almost 10 million sentences. Print as you go instead of storing them.
• Watch the spaces. Joining with String.join avoids a space at the start or the end.

What interviewers ask next

• Phone keypad letters (LeetCode 17)? Each digit is a list of 3 or 4 letters. Exactly the same recursion.
• Without recursion? Keep an index for each list, like a car's mileage counter: print, then add one to the last index, and when it rolls over, reset it and add one to the index before it.
• Give the kth sentence directly? Treat k as a number with a different base for each list: the last list's index is k % size, then divide and move left.
• Skip sentences that break a rule, like the same word twice? Check before going down, so a bad branch is cut early. That is pruning.

Remember this

Grown-up words: picking one item from each list is the Cartesian product, the menu tree is a recursion tree, choose and undo is backtracking, and the waiting line in Way 1 is a queue used level by level, like breadth first search.