Word Break Problem: A Dynamic Programming Approach

The "Word Break" problem is a popular question in dynamic programming. It involves determining whether a given string can be segmented into a sequence of one or more dictionary words.

Problem Statement

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Example

• Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: The string "leetcode" can be segmented as "leet code".

• Input: s = "applepenapple", wordDict = ["apple", "pen"] Output: true Explanation: The string can be segmented as "apple pen apple".

Dynamic Programming Solution

Breaking Down the Solution

• Initialize dp Array: Create an array dp of length s.length + 1 and initialize all elements to false, except dp[0], which is true.
• Dynamic Programming Iteration: Iterate through the string s. For each position i, check all substrings ending at i. If any substring is found in wordDict and the remaining part of the string up to the start of the substring is also breakable (as indicated by dp), mark dp[i] as true.
• Check for Word Break: Return the value of dp[s.length]. If it's true, it means the string s can be segmented into words from the dictionary.

Conclusion

The Word Break problem is an excellent application of dynamic programming to solve string manipulation challenges. It shows how problems can be solved by breaking them down into smaller, more manageable subproblems, and then combining these solutions to solve the larger problem.

Rust Solution

Rust must annotate the collected type — HashSet<&str> — and it holds borrowed &str slices produced by word_dict.iter().map(|w| w.as_str()).collect(), so the set points into word_dict rather than owning fresh copies (unlike JS's untyped new Set(wordDict)). vec![false; n + 1] builds the dp table in one macro, and the inclusive range 1..=n mirrors the dp[i] indexing while 0..i stays exclusive. Membership is word_set.contains(&s[j..i]), where &s[j..i] is a byte-index string slice borrowed straight out of s. The function's final expression dp[n] is the return value, with no return keyword.

Go Solution

Go has no built-in set type, so map[string]bool{} fills that role, populated by for _, w := range wordDict with the blank identifier _ discarding the loop index. make([]bool, len(s)+1) allocates dp already zeroed to false, so unlike JS's .fill(false) only dp[0] needs setting explicitly. Membership is a bare map read — set[s[j:i]] returns the zero value false for an absent key, so the comma-ok v, ok := m[k] form is unnecessary to test presence. s[j:i] slices the string by byte index, and return dp[len(s)] yields the answer.