DSA interview question

Word Break

Medium · Algorithms · Topics: recursion, dp, trie

The problem

A search engine receives queries typed without spaces, like "applepenapple", and needs to know whether the text can be split into a sequence of dictionary words (words may be reused). The recursive idea is simple: try every dictionary word that matches at the current position and recurse on the rest. But the same suffix gets re-examined again and again, which is exponential for inputs like "aaaa…ab". Remembering the answer for each start position (memoisation) makes it O(n · L) substring checks, where L is the longest word.

Example: "leetcode", dictionary ["leet", "code"] → true.

Function signature

bool wordBreak(const string& s, const vector<string>& wordDict);

Test cases

Input `(s, dict)`	Output	Explanation
`("leetcode", [leet, code])`	`true`	leet + code
`("applepenapple", [apple, pen])`	`true`	Words can be reused
`("catsandog", [cats, dog, sand, and, cat])`	`false`
`("aaaaaaa", [aaaa, aaa])`	`true`	aaa + aaaa
`("aaaaaaaaaaaaaaaaaaaaaaaaaaaaab", [a, aa, aaa, aaaa])`	`false`	Exponential without memoisation

(Confirm: dictionary words can be reused; the whole string must be used; words are distinct and non-empty.)

How interviewers phrase it

"Given a string s and a dictionary of words, return true if s can be segmented into a space-separated sequence of one or more dictionary words" (LeetCode 139).
Listing every segmentation is Word Break II (LeetCode 140).

Clarifying questions to ask

Can words be reused? (Yes.)
How large are s and the dictionary? (s up to about 300 characters.)
Do I need the segmentation, or just true/false?

Follow-ups to expect

"What's the plain recursion?"
"Why does memoisation work?"
"Bottom-up version?"
"How do you speed up the dictionary lookups?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview