Determine if a string can be segmented
Company: TikTok
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a string `s` and a list of strings `wordDict`, determine whether `s` can be segmented into a sequence of one or more dictionary words.
- You may reuse dictionary words multiple times.
- Return `true` if such a segmentation exists, otherwise return `false`.
### Input
- `s`: a non-empty string
- `wordDict`: a list of non-empty strings
### Output
- Boolean indicating whether `s` can be segmented.
### Example
- `s = "leetcode"`, `wordDict = ["leet", "code"]` → `true`
- `s = "catsandog"`, `wordDict = ["cats","dog","sand","and","cat"]` → `false`
### Notes / constraints (typical interview assumptions)
- `1 <= len(s) <= 10^4`
- `1 <= len(wordDict) <= 10^5`
- Total characters across `wordDict` can be large; aim for an efficient solution.
Quick Answer: This question evaluates a candidate's understanding of dynamic programming and string-processing skills, along with algorithmic complexity analysis for segmentation problems.
Return whether s can be segmented into dictionary words, allowing reuse.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ('leetcode', ['leet','code'])
Expected Output: True
Explanation: Prompt true example.
Input: ('catsandog', ['cats','dog','sand','and','cat'])
Expected Output: False
Explanation: Prompt false example.
Input: ('aaaaaaa', ['aaaa','aaa'])
Expected Output: True
Explanation: Reusable words.
Hints
- Model object-style prompts as operation streams when needed.
- Handle empty and boundary cases before the main logic.