Contents

1. 1. Introducation
2. 2. My Solution
3. 3. Result

Introducation

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:

Input:
s = “catsanddog”
wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]
Output:
[
“cats and dog”,
“cat sand dog”
]
Example 2:

Input:
s = “pineapplepenapple”
wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”]
Output:
[
“pine apple pen apple”,
“pineapple pen apple”,
“pine applepen apple”
]
Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:

Input:
s = “catsandog”
wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
Output:
[]

My Solution

Key: Backtracking and Dynamic Programming, recursion, get result from the tail and save for previous breaks use.

O(n): n

type mybreak struct {
	ends []int
}

func findBreaks(s string, wordDict []string) []mybreak {
	n := len(s)
	mybreaks := make([]mybreak, n)
	for i := 0; i < n; i++ {
		for _, v := range wordDict {
			if len(v) <= (n - i) { // no out of index
				if strings.Compare(s[i:i+len(v)], v) == 0 {
					mybreaks[i].ends = append(mybreaks[i].ends, i+len(v))
				}
			}
		}
	}
	return mybreaks
}

var myresults map[int][]string

func mySearch(s string, mybreaks []mybreak, i int) {
	strs := make([]string, 0)
	if len(mybreaks[i].ends) == 0 {
		myresults[i] = strs
		return
	}
	for _, v := range mybreaks[i].ends {
		str := s[i:v]
		if v == len(s) {
			strs = append(strs, str)
			continue
		}
		_, ok := myresults[v]
		if !ok {
			mySearch(s, mybreaks, v)
		}
		for _, v2 := range myresults[v] {
			tmpstr := str + " " + v2
			strs = append(strs, tmpstr)
		}
	}
	myresults[i] = strs
}
func wordBreak(s string, wordDict []string) []string {
	mybreaks := findBreaks(s, wordDict)
	myresults = make(map[int][]string)
	mySearch(s, mybreaks, 0)
	return myresults[0]
}

Result

39 / 39 test cases passed.
Status: Accepted
Runtime: 4 ms
Memory Usage: 2.9 MB