[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