Can a string be built by concatenating words from a list (words may repeat)? How do you answer yes or no, and how do you also return which words?

29.1.6 · L3 · Interview

Reported at: Google

Predict first

What does the prefix table print for these four inputs?

func segment(_ s: String, _ words: [String]) -> [String]? {
    let chars = Array(s), dict = Set(words), n = chars.count
    if n == 0 { return [] }
    var reach = [Bool](repeating: false, count: n + 1)
    var prev = [Int](repeating: 0, count: n + 1)       // start of the last word that ends here
    reach[0] = true
    for end in 1...n {
        for start in 0..<end where reach[start] && dict.contains(String(chars[start..<end])) {
            reach[end] = true; prev[end] = start; break
        }
    }
    guard reach[n] else { return nil }
    var out: [String] = []
    var i = n
    while i > 0 { out.append(String(chars[prev[i]..<i])); i = prev[i] }
    return out.reversed()
}
func show(_ r: [String]?) -> String { r.map { $0.joined(separator: " + ") } ?? "impossible" }
print(show(segment("applepenapple", ["apple", "pen"])))
print(show(segment("catsandog", ["cats", "dog", "sand", "and", "cat"])))
print(show(segment("leetcode", ["leet", "code"])))
print(show(segment("aaaa", ["aa", "aaa"])))
  • apple + pen + apple / impossible / leet + code / aa + aa
  • apple + pen + apple / cats + and + og / leet + code / aa + aa
  • impossible for all four

Mental model. Laying paving stones from the left: you mark every distance you can reach exactly, and from each marked distance you try every stone that fits. The last marked distance equal to the path length means it can be done.

A recursive “try every first word” search repeats the same suffixes exponentially often. Make it dynamic programming over prefixes: reach[i] means the first i characters can be built. reach[0] is true; for each end position, try every start where reach[start] is true and the slice start..<end is in the word set. That is O(n²) slices (each costing up to O(n) to hash, so O(n³) in the worst case, which you state) and O(n) memory, with the word set making each lookup O(1) on average. The answer is reach[n].

To return which words, store for each reachable end the start of the last word (prev[end] = start) and walk back from n, then reverse; the check prints apple + pen + apple, says impossible for "catsandog", and finds aa + aa for "aaaa" (any valid split is acceptable unless the interviewer asks for all). Name the optimisation of limiting the inner loop to the longest word length, and mention that returning all splits is exponential in the worst case. Reported at Google (anonymous, unverified).

The table finds a split when one exists, reports impossible for catsandog, and reconstructs the words by walking back from the end.

Common traps

  • Plain recursion without memoisation. It times out on strings like "aaaa…ab".
  • Using an array for the dictionary. Look-ups should be a Set.

They might follow up with

  • How do you cut the cost? Only test slices up to the longest word length.
  • What if you must return every possible sentence? Backtracking with memoisation on the suffix; the output itself can be exponential.

Related questions

  • 29.1.5 Given a string with brackets, remove the fewest parentheses to make it valid. How do you count them, and how…
  • 29.1.8 When do you use a sliding window, and how do the fixed-size and variable-size versions differ?
  • 29.2.2 Implement a hash map from scratch (get, set, remove), then extend it: what do you test and how does resizing…

← Given a string with brackets, remove the fewest parentheses to make…   Next permutation: rearrange an array into the next lexicographically… →