How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Determine string segmentability with dictionary

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Determine string segmentability with dictionary states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given a string s and a dictionary of words, determine whether s can be segmented into a sequence of dictionary words. Provide a dynamic-programming solution and then propose an alternative that uses a Trie to speed up prefix checks and early termination on long inputs. Discuss complexity, memory trade-offs, and how to return one valid segmentation (or all possible segmentations).

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Determine string segmentability with dictionary states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given a string `s` and a list of words `word_dict`, return `true` if `s` can be segmented into a space-separated sequence of one or more words from `word_dict`. The same dictionary word may be reused any number of times. An empty string is considered segmentable (it is the empty concatenation). Example 1: s = "leetcode", word_dict = ["leet", "code"] -> true ("leet code"). Example 2: s = "applepenapple", word_dict = ["apple", "pen"] -> true ("apple pen apple"; "apple" is reused). Example 3: s = "catsandog", word_dict = ["cats", "dog", "sand", "and", "cat"] -> false. The classic O(n^2) approach is bottom-up dynamic programming: dp[i] is true iff the prefix s[:i] can be segmented; dp[i] becomes true when some split point j has dp[j] true and the substring s[j:i] is in the dictionary. An alternative builds a Trie over the dictionary so prefix checks share work and the inner scan can terminate early once no dictionary prefix matches; the Trie keeps the same worst-case time but trades extra memory for fewer redundant substring lookups on long inputs.

Constraints

1 <= len(s) <= 300 (an empty s returns True)
1 <= word_dict.length <= 1000 (an empty dictionary is allowed; only the empty string is then segmentable)
1 <= each word length <= 20
s and all dictionary words consist of lowercase English letters
Dictionary words may be reused any number of times

Examples

Input: ("leetcode", ["leet", "code"])

Expected Output: True

Explanation: "leet" + "code" covers the whole string.

Input: ("applepenapple", ["apple", "pen"])

Expected Output: True

Explanation: "apple" + "pen" + "apple"; the word "apple" is reused.

Input: ("catsandog", ["cats", "dog", "sand", "and", "cat"])

Expected Output: False

Explanation: No segmentation reaches the end: "cats"+"and" leaves "og", and "cat"+"sand" leaves "og", neither of which is in the dictionary.

Input: ("", ["a", "b"])

Expected Output: True

Explanation: Edge case: the empty string is the empty concatenation, so it is segmentable.

Input: ("aaaaaaa", ["aaaa", "aaa"])

Expected Output: True

Explanation: 7 = 4 + 3, so "aaaa" + "aaa" works despite heavy overlap between candidate splits.

Input: ("a", [])

Expected Output: False

Explanation: Edge case: an empty dictionary cannot cover any non-empty string.

Input: ("bb", ["a", "b", "bbb", "cccc"])

Expected Output: True

Explanation: "b" + "b"; a single-letter word reused covers the string even though "bb" itself is not in the dictionary.

Hints

Define dp[i] = True iff the prefix s[:i] can be segmented. dp[0] = True because the empty prefix is trivially segmentable.
For each end index i, look back to a split point j: if dp[j] is True and s[j:i] is a dictionary word, then dp[i] is True.
Put the dictionary in a hash set for O(1) membership, and bound the inner loop by the longest word length so you never test substrings longer than any dictionary word.
For the Trie variant, walk the Trie from each start position; stop the inner scan as soon as no child matches the next character (early termination), which speeds up long inputs with few matching prefixes.

Quick Overview