FastPrepFirst Valid Word Segmentation
Problems/First Valid Word Segmentation

First Valid Word Segmentation

Amazon logoAmazon● MediumFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an Amazon full-time onsite interview. The report asks for one way to split a continuous lowercase string into words by backtracking, using an isWord check, and it promises a solution exists. It does not give the dictionary format, the number limits, or a tie rule for when several splits work. Our version is about 95% the same as the reported question.

Given a continuous lowercase string s and an array dictionary representing the words accepted by isWord, split s into a sequence of dictionary words whose concatenation is exactly s.

At each position, consider possible next words by increasing end position, so the shortest possible next prefix is tried first. Return the first complete segmentation found by that order. At least one valid segmentation is guaranteed.

Function

segmentWords(s: String, dictionary: String[]) → String[]

Examples

Example 1

s = "myhousehavecat"dictionary = ["my","house","have","cat"]return = ["my","house","have","cat"]

Each returned piece is accepted by the dictionary, and their concatenation is myhousehavecat.

Example 2

s = "aaaa"dictionary = ["a","aa"]return = ["a","a","a","a"]

Both one- and two-character words are valid, but increasing end positions try a before aa. Repeating that choice reaches a complete segmentation.

Example 3

s = "catsanddog"dictionary = ["cats","dog","sand","and","cat"]return = ["cat","sand","dog"]

At index 0, cat ends before cats and can lead to a complete segmentation, so it begins the returned sequence.

Constraints

  • 1 <= s.length <= 500, and s contains only lowercase English letters.
  • 1 <= dictionary.length <= 5000.
  • Dictionary words are distinct, contain only lowercase English letters, and have lengths from 1 through 50.
  • The total number of characters across dictionary is at most 10^5.
  • At least one valid segmentation of s exists.
  • Possible next words are considered by increasing end position.
See Amazon hiring insights
Saved
class Solution {
    public String[] segmentWords(String s, String[] dictionary) {
        // write your code here
    }
}
Checking account…