The Question

Word Break

Given a non-empty string s and a list of strings wordDict containing a dictionary of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words and each word can be reused multiple times in the segmentation. Example: Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code". Constraints: - 1 <= s.length <= 300 - 1 <= wordDict.length <= 1000 - 1 <= wordDict[i].length <= 20 - s and wordDict[i] consist of only lowercase English letters.

Java

HashSet

Questions & Insights

Clarifying Questions

Can dictionary words be reused? Yes, words in the wordDict can be used multiple times in the segmentation.

Is the comparison case-sensitive? Usually, yes, "Apple" and "apple" would be distinct unless specified.

What are the constraints on the length of the string and the size of the dictionary? This helps determine if an

O(n^2)

O(n^3)

approach is acceptable versus needing a Trie-based optimization.

What should be returned for an empty string? Typically, an empty string is segmentable if the logic treats it as a base case, but usually, the input s will have a minimum length of 1.

Assumptions:

The input string s consists of lowercase English letters.

The dictionary contains unique words.

1 \le s.length \le 300

1 \le wordDict.length \le 1000

Thinking Process

Identify Subproblems: To know if string

S[0...i]

is segmentable, we need to find some

j < i

such that

S[0...j]

is segmentable AND the substring

S[j...i]

exists in the dictionary.

Define State: Use a boolean array dp where dp[i] represents whether the prefix of length i.e., s.substring(0, i)) can be segmented into dictionary words.

State Transition: For each position i from 1 to n, check all previous positions j. If dp[j] is true and the substring from j to is in the wordDict, then dp[i] becomes true.

Optimization: Use a HashSet for the dictionary to achieve

O(1)

average time complexity for word lookups.

Implementation Breakdown

Problem Set

Functional Requirement: Return true if the input string can be segmented; otherwise, return false.

Constraint: The solution must handle strings up to 300 characters efficiently.

Boundary Condition: dp[0] must be initialized to true as the base case for the empty prefix.

Approach

Algorithm: Dynamic Programming (Bottom-Up).

Data Structure: HashSet for

O(1)

lookups, boolean[] for state tracking.

Complexity:

Time:

O(n^2 \cdot k)

where

n

is the length of the string and

k

is the average length of the substring operation (in Java, substring is

O(k)

Space:

O(n + m)

where

n

is the DP array and

m

is the space for the dictionary in the set.

Implementation

Wrap Up

Advanced Topics

Trie Optimization: If the dictionary is very large and the string is long, we can use a Trie to check valid substrings. Instead of checking all

j < i

, we can traverse the Trie using characters from

s[i...n]

to find valid words starting at

i

DFS with Memoization: This can be solved top-down. Memoization ensures that we don't re-calculate the same suffix multiple times, effectively yielding the same complexity as DP.

Space-Time Trade-off: If memory is tight, a recursive approach with a limited-depth cache might be preferred over a full DP table, though in this specific problem,

O(n)

space is generally negligible.