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 s = “leetcode”, dict = [“leet”, “code”].

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

UPDATE (2017/1/4): The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

s思路： 1. 看到第一眼，想是不是要遍歷所有可能的word break。例如：s = “leetcode”, 以”l”開頭的一個一個查表看有沒有”l”,”le”,”lee”,”leet”,剛好，發現有一個”leet”,然后recursive進入下一個層次找以”c”開頭的單詞了；看起來沒毛病，但這只是故事的一部分。完整版本是，如果發現字典有”l”,”eet”,那么還可以通過遍歷”l”和”eet”之后也進入到查找以”c”開頭的單詞是否可以在字典中找到。敘述到這里，也就是說判斷以”c”開頭的單詞是否可以在字典中就要進行兩次，也就是說，我們發現重復計算的情況出現。 2. 重復計算，那么就要用DP.每次計算好某一個位置起始是否可以做到word break, 把結果保存起來，一方便重復使用! 3. 瞄了一眼hint，用dp。之前有總結，如果判斷是與非的問題，對整個問題的判斷依靠對局部問題的判斷，也就是：整個string要能break，那么其部分也應該可以break。這樣的問題，就可以用dp,把大的問題劃分成小的問題。 4. 再把自己粗糙的思路寫一下：剛開始嘗試用2d的DP來做，發現大部分地方是零，做起來很別扭；然后換成1d的DP來寫，一下就順暢了。給我的啟發就是，確定dp后，不知道是用1d還是2d，那就都嘗試一下，哪個寫起來順暢就是哪個。當然背后肯定有硬道理了。 5. 思考什么時候用1d，什么時候2d的DP？