Skip to content
Katabench
Try free

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 performance bar

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

C#
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.

C# coding challenges →

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