Funcia
Lv.3dphashstring

Word Break

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Given a string s without spaces and a dictionary words, return whether s can be split into pieces that are all dictionary words (words may be reused).

Examples

swordsresult
"applepenapple"["apple", "pen"]true
"catsandog"["cats", "dog", "sand", "and", "cat"]false
"aaaaaaa"["aaa", "aaaa"]true

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(s: string, words: string[]) → bool

Constraints

  • 1≤1 \le s.length ≤100,000\le 100{,}000, 1≤1 \le words.length ≤1,000\le 1{,}000, 1≤1 \le words[i].length ≤20\le 20
  • Lowercase English letters only; the dictionary may contain duplicates.

Expected complexity

Time
O(N * L)
Space
O(N + total word length)

Examples

swordsExpected
"applepenapple"["apple","pen"]true
"catsandog"["cats","dog","sand","and","cat"]false
"aaaaaaa"["aaa","aaaa"]true

Hint

Hint

DP over prefixes: ok[0] = true, and ok[i] holds if some word w ends at i with ok[i - |w|]. Because words are at most 20 letters, only check pieces of length 1..20 (hash set) or walk a trie forward from each true position. Checking every earlier split point creates O(N2)O(N^2) substrings and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.