未分類

Word Break

DynamicProgramming, Go, LeetCode

Word Break

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. You may assume the dictionary does not contain duplicate words.

For example:

Given

1
2
s = "leetcode",
dict = ["leet", "code"].

Return true because “leetcode” can be segmented as “leet code”.

提示 解題應用
DynamicProgramming 規律觀查

Default:

1
2
3
func wordBreak(s string, wordDict []string) bool {
}

解答思路:

一開始想到兩種作法，組合或是消除法，如果要用字典檔的詞來組合一來是會花費大量的時間，二來是字典檔也會包含亳不相關的詞(只要字典檔有包含結果的組合就好，且可重覆使用)，而如果使用消除法也就是如果字典檔的詞在字串之中就把字串中的該詞消除掉，然而最大的問題是像cac,[c,ca]，如果把開頭的c先消除就會導致後續沒辦法把剩下的a給消除(因為只能消除ca)，也就是說很難控制確定要消除的位置，如果再用遞回處理所有可能的情況一樣會花費大量的時間，所以最後用標註法也許是比較好的辦法，如果字典檔的詞在字串之中就把字串中的該詞所在的位置給標註起來而非消除，以剛才的例子來說:

字串: cac 字典檔: [c,ca]

第1個在字典檔在存在 標註1的位置

1
"c"ac

第1~2個在字典檔在存在 標註2的位置

1
"ca"c

第1~3個在字典檔在不存在 跳過

1
"cac"

第2~3個在字典檔在不存在 跳過

1
c"ac"

第3個在字典檔在存在 標註3的位置

1
ca"c"

唯一要注意到的是在標註前都要檢查前一個的位置是否已標註存在，要從頭慢慢往後標註而非跳著做標註，如此一來才能確保前面的字串都能藉由字典檔的詞依序組出，標註結束後只要檢查最後一個位置是否有被標註就可以知道該字串是否能由字典檔組合出來了。

程式碼解說:

既然要用標註的方法來紀錄字典檔的詞是否在字串之中，一開始就先初始化對應字串長度的boolean陣列，不過因為標註前都要檢查前一個的位置是否已標註存在，但最開頭的標註並沒有前一個可以判斷，所以標註的陣列就需要再多一格來當作開頭前一個並存放true以確保後續操作上的一致性，接著就是以巢狀迴圈從字串中取出子字串(i為子字串結尾位置的下一個，j則是子字串開頭位置)，再以一迴圈從字典檔中一一取詞做比對，如果前一個標註的位置存在(“前一個子字串結尾位置的下一個i”來代表詞的標註位置與下一個”子字串開頭位置j”相同)且子字串與字典檔的詞相同，就在i的位置標註為true並跳開兩層內層的迴圈以找出下一個字典檔對應的詞，待標註全數結束後只要檢查最後一個位置是否有被標註就可以知道該字串是否能由字典檔組合出來了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var substring string
exist := make([]bool, len(s)+1)
exist[0] = true
for i := 1; i <= len(s); i++ {
	for j := 0; j < i; j++ {
		substring = s[j:i]
		for _, v := range wordDict {
			if exist[j] && v == substring {
				exist[i] = true
				break
			}
		}
		if exist[i] {
			break
		}
	}
}
return exist[len(s)]

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func wordBreak(s string, wordDict []string) bool {
	var substring string
	exist := make([]bool, len(s)+1)
	exist[0] = true
	for i := 1; i <= len(s); i++ {
		for j := 0; j < i; j++ {
			substring = s[j:i]
			for _, v := range wordDict {
				if exist[j] && v == substring {
					exist[i] = true
					break
				}
			}
			if exist[i] {
				break
			}
		}
	}
	return exist[len(s)]
}

總結:

要判斷字典檔中的詞是否能組出目標字串，做法是字典檔的詞如果在字串之中就把字串中的該詞所在的位置給標註起來，而要注意到的是在標註前都要檢查前一個的位置是否已標註存在，要從頭慢慢往後標註而非跳著做標註，如此一來才能確保前面的字串都能藉由字典檔的詞依序組出，標註結束後只要檢查最後一個位置是否有被標註就可以知道該字串是否能由字典檔組合出來了。

分享到