Word Break

Medium

The problem

Return true if the string s can be cut into pieces so that every piece is a word from wordDict. Words from the dictionary can be used as many times as you like.

Example 1
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
"leet" + "code".
Example 2
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
"apple" + "pen" + "apple" (reusing a word is fine).
Example 3
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
No cut leaves only dictionary words; "cats" + "and" leaves "og".

Limits

1 ≤ len(s) ≤ 300
1 ≤ len(wordDict) ≤ 1,000
Each word has 1 to 20 lowercase letters

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Can the prefix of length i be built? It can if some earlier prefix can AND the piece in between is a word.

The idea

dp[0]=true; dp[i] = any j < i with dp[j] and s[j:i] in the dictionary.

Target: O(n² · L) time

Go function shape

func wordBreak(s string, wordDict []string) bool

Reference solution

Tested with go test. Try it yourself first, then compare.

// WordBreak: can s be split into dictionary words?
// dp[i] = the first i letters can be split, true when some earlier cut j works AND s[j:i] is a word.
func WordBreak(s string, words []string) bool {
	dict := make(map[string]bool, len(words))
	for _, w := range words {
		dict[w] = true
	}
	dp := make([]bool, len(s)+1)
	dp[0] = true
	for i := 1; i <= len(s); i++ {
		for j := 0; j < i; j++ {
			if dp[j] && dict[s[j:i]] {
				dp[i] = true
				break
			}
		}
	}
	return dp[len(s)]
}

Read the lesson: Dynamic Programming