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 easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

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

Solve Two String Problems | Amazon Coding Question

Quick Overview

This task evaluates string manipulation and encoding for generating unique Morse representations, along with sentence segmentation and combinatorial enumeration for producing all valid word-break sentences, focusing on transformation, deduplication, and decomposition skills.

Loading coding console...

Part 2: Word Break II

Given a string s and a dictionary of valid words wordDict, insert spaces into s to form every possible sentence such that each segmented word appears in the dictionary. Return all valid sentences sorted lexicographically for consistent testing. If no sentence can be formed, return an empty list.

Constraints

0 <= len(s) <= 20
0 <= len(wordDict) <= 1000
1 <= len(wordDict[i]) <= 10 for every dictionary word when the list is non-empty
s and all words in wordDict contain only lowercase English letters
A dictionary word may be reused multiple times

Examples

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

Expected Output: ["cat sand dog", "cats and dog"]

Explanation: There are exactly two valid ways to split the string.

Input: ("pineapplepenapple", ["apple", "pen", "applepen", "pine", "pineapple"])

Expected Output: ["pine apple pen apple", "pine applepen apple", "pineapple pen apple"]

Explanation: Three different valid segmentations exist.

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

Expected Output: []

Explanation: No full segmentation reaches the end of the string.

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

Expected Output: []

Explanation: For this problem, empty input returns no sentences.

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

Expected Output: ["a"]

Explanation: The whole string itself is a valid dictionary word.

Hints

Think of the problem as: from each starting index, what sentences can be formed from the suffix beginning there?
Use memoization so you do not recompute all sentence combinations for the same index repeatedly.

Quick Overview