Split a string into dictionary words
Determine whether a string can be segmented completely into one or more words from a supplied dictionary.
Course progress
Problem 94 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
text = "buildquill"; words = ["build", "quill", "code"]
Expected output
True
What is happening?
The prefix build is a dictionary word and leaves quill, which is also present. The entire string can therefore be segmented.
Solution strategy
Build the right mental model
Mark each reachable prefix. From every reachable split point, test whether the following substring is a dictionary word.
Core concepts
dynamic programming · hash set
Complexity
Time O(n^3) with substring creation, space O(n + dictionary size).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for word-break
using System;
using System.Collections.Generic;
class Program
{
static bool CanSegment(string text, HashSet<string> words)
{
bool[] reachable = new bool[text.Length + 1];
reachable[0] = true;
for (int end = 1; end <= text.Length; end++)
for (int start = 0; start < end; start++)
if (reachable[start] && words.Contains(text.Substring(start, end - start)))
{ reachable[end] = true; break; }
return reachable[text.Length];
}
static void Main()
{
var words = new HashSet<string> { "build", "quill", "code" };
Console.WriteLine(CanSegment("buildquill", words));
}
}Knowledge check
Questions students often ask
What is the main idea behind split a string into dictionary words?
Mark each reachable prefix. From every reachable split point, test whether the following substring is a dictionary word.
What is the time and space complexity of this solution?
Time O(n^3) with substring creation, space O(n + dictionary size).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.