[LeetCode] 139. Word Break

轉自LeetCode

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

<Solution>

這題用 dynamic programing 來解(參考資料1, 參考資料2)

dp[i]=true 代表的是，可以在 s[i] 這個位置插入一個空白

例如 dp[4] = true，則可以在 s[4] 插入一個空白: leetcode -> leet code

為了方便，這邊的 index 不用 0 到 s.length() - 1，而是 1 到 s.length()

當dp[j] = false，代表以 s[j] 結尾的 substr 是不在 dict 裡，不可能在那裡插空白

因此就可以省略此 substr 以及去 set 查的動作

另外，此題只是想知道能不能把 s 切成 dict 裡面的字串，並沒有要找總共有多少切法

所以一旦找到某一種切法，就可以先結束此次的 iteration

Kotlin

	class Solution {
	fun wordBreak(s: String, wordDict: List<String>): Boolean {
	val table= wordDict.toHashSet()
	//dp[i] means you can insert a space in the position i of s
	val dp = BooleanArray(s.length + 1)
	dp[0] = true // you can see this as a space befoer s[0]
	for(i in 1..s.length) {
	for(j in 0 until i) {
	if(dp[j] && table.contains(s.substring(j,i))) {
	dp[i] = true
	break
	}
	}
	}
	// if we can insert a space after s[s.lastIndex], means it meets the requirement
	return dp[s.length]
	}
	}

view raw word_break.kt hosted with ❤ by GitHub