Facebook PixelWord Break — Coding Practice
Word BreakMedium

Word Break

Medium 16.1k46% acceptance
Hash TableStringDynamic ProgrammingTrie

Given a string s and a list of words wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Words from the dictionary may be reused any number of times, and not every dictionary word has to be used.

Example 1
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
"leetcode" splits into "leet code".
Example 2
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
"apple pen apple" — note "apple" is reused.
Example 3
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
No segmentation covers the whole string; "catsand" leaves "og" with no match.
Constraints
  • 1 ≤ s.length ≤ 300
  • 1 ≤ wordDict.length ≤ 1000
  • All strings are lowercase English letters; dictionary words are distinct.
Asked atAmazonGoogleMetaBloomberg
JavaScript
Loading editor…
Case 1
"leetcode", ["leet","code"]
expected: true
Case 2
"applepenapple", ["apple","pen"]
expected: true
Case 3
"catsandog", ["cats","dog","sand","and","cat"]
expected: false
Case 4
"a", ["a"]
expected: true
Case 5
"ab", ["a"]
expected: false
Case 6
"cars", ["car","ca","rs"]
expected: true
Case 7
"aaaaaaa", ["aaaa","aaa"]
expected: true