MediumDpAI interview only
Word Break
Asked atamazongooglemetamicrosoftbloombergappleuber
01 · Problem
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
02 · Examples
Example 01
Input
s = "leetcode", wordDict = ["leet","code"]
Output
true
"leetcode" can be split as "leet" + "code", both of which are in the dictionary.
Example 02
Input
s = "applepenapple", wordDict = ["apple","pen"]
Output
true
"applepenapple" can be split as "apple" + "pen" + "apple". Dictionary words can be reused.
03 · Constraints
- 011 <= s.length <= 300
- 021 <= wordDict.length <= 1000
- 031 <= wordDict[i].length <= 20
- 04s and wordDict[i] consist of only lowercase English letters
- 05All the strings of wordDict are unique
04 · Optimal complexity
- Time
- O(n^2 * m)
- Space
- O(n)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.