Quick Overview

Decide whether an entire string can be segmented into reusable dictionary words. Handle overlapping candidates, the empty string, and large inputs with a dynamic program or graph search that avoids enumerating all possible segmentations.

Determine Whether a String Can Be Segmented into Dictionary Words

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

## Problem Given a string and a set of words, return whether the entire string can be formed by concatenating dictionary words. A dictionary word may be reused any number of times. Every character of the input string must belong to exactly one chosen segment. ### Constraints & Assumptions - The string length is at most 10,000. - The dictionary contains at most 5,000 non-empty lowercase words. - Duplicate dictionary entries have no additional effect. - The empty input string is segmentable. ### Clarifications - The function returns a boolean and does not need to enumerate segmentations. - Words may overlap as candidates, but selected segments cannot overlap. - The same word can appear in multiple positions. ### Examples ```text s = "applepenapple", words = ["apple", "pen"] output = true s = "catsandog", words = ["cats", "dog", "sand", "and", "cat"] output = false ``` ### Hints ```hint Choose a state boundary Track which prefixes are fully constructible rather than committing greedily to the longest word. ``` ```hint Limit candidate lengths The longest dictionary word can bound how far back each transition must inspect. ```

Overview: Decide whether an entire string can be segmented into reusable dictionary words. Handle overlapping candidates, the empty string, and large inputs with a dynamic program or graph search that avoids enumerating all possible segmentations.

Read the full Meta Software Engineer interview experience this question came from

Given a string and a dictionary of non-empty lowercase words, return whether the entire string can be formed by concatenating dictionary words. A word may be reused any number of times, duplicate dictionary entries have no extra effect, and every input character must belong to exactly one selected segment. The empty string is segmentable.

Constraints

  • len(s) <= 10000.
  • The dictionary contains at most 5000 non-empty lowercase words.
  • Duplicate dictionary entries have no additional effect.
  • A dictionary word may be reused any number of times.
  • Every input character must belong to exactly one selected segment.
  • The empty input string is segmentable.

Examples

Input: ('applepenapple', ['apple', 'pen'])

Expected Output: True

Explanation: This is the first source example; apple can be reused around pen.

Input: ('catsandog', ['cats', 'dog', 'sand', 'and', 'cat'])

Expected Output: False

Explanation: This is the second source example; no choices cover the entire suffix.

Hints

  1. Track which string boundaries can be reached by complete dictionary words.
  2. A trie lets each reachable boundary explore only prefixes that occur in the dictionary.

Loading coding console...

Show the approach

Approach

Build a trie for the dictionary so candidate words sharing prefixes can be explored without repeatedly testing unrelated words. Let reachable[i] mean the prefix ending just before position i is fully segmentable, with reachable[0] true. From every reachable start, walk forward through the trie until the current characters stop matching a dictionary prefix. Whenever a terminal trie node is reached, mark the following string boundary reachable. Every mark appends one valid dictionary word to a valid prefix, and conversely every valid segmentation follows trie edges from one reachable boundary to the next. Therefore the whole string is segmentable exactly when its final boundary becomes reachable.

Time complexity:
O(D + nL) worst case, where D is total dictionary characters and L is the longest word
Space complexity:
O(D + n)