You’re interviewing for a backend or data engineering role at a FAANG-level company. The interviewer describes a real product scenario:
A large search or content platform needs to split user input into meaningful tokens for indexing, recommendations, and query understanding. The platform has a trusted dictionary of known words, such as:
- product categories
- search keywords
- known entities
- allowed tags
A user input string s arrives without spaces because it may come from logs, URLs, or compact identifiers. The platform wants to determine if the string can be segmented into a sequence of dictionary words.
This is a common practice coding problem for DSA question might ask in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.
Your Task
Given a string s and a list of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
You may reuse words in wordDict multiple times.
Input Format
s: a stringwordDict: a list of strings representing valid dictionary words
Output Format
- A boolean value
true if s can be segmented using the dictionaryfalse otherwise
Examples
Example 1:
Input: s = "leetcode"
wordDict = ["leet","code"]
Output: true
Example 2:
Input: s = "applepenapple"
wordDict = ["apple","pen"]
Output: true
Example 3:
Input: s = "catsandog"
wordDict = ["cats","dog","sand","and","cat"]
Output: false