Word Break
Medium About 20 min Free, no account needed
Can the string be segmented into dictionary words?
The brief
Given a string s and a dictionary wordDict, return true if s can be
split into a sequence of dictionary words (reuse allowed).
The obvious approach tries every matching prefix recursively. On a negative case
like 60 as followed by b with dictionary ["a", "aa", "aaa"], the
recursion revisits the same suffixes exponentially many times, far too slow.
You need to avoid recomputing the same suffix repeatedly, bringing it down to
about O(n2 * dict).
Starter code
using System;
public class Solution
{
// TODO: return true when s can be segmented into dictionary words.
public bool WordBreak(string s, string[] wordDict)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Dynamic programming
- Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.
- Hash maps and sets
- Trade memory for constant-time lookups, membership tests and frequency counts.
Related katas
- Coin Change (Fewest Coins) Medium Free The fewest coins that make the amount, or -1.
- Coin Change II (Count the Ways) Medium Free How many coin combinations make the amount?
- Contiguous Array Medium Free Longest subarray holding as many zeros as ones.
- Decode Ways Medium Free How many letter strings could this digit string encode?