LeetCode Q139: Word Break

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:

In my first try, I mistakenly compare current substr with ones in the dictionary. If matching, remove the substr from given string and keep matching the remaining part. However, it is not necessarily the correct answer. For example, when s="aaaaaaa", dict=["aaaa", "aaa"], in which the algorithm will match "aaa", "aaa" first, then left only one "a" in s which will result in a failed matching.

So, think of using DP and recursion.

Round 2 solution: