题目
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".
思路
- 这道题开始想的时候本来觉得用2pointer能做的，但是写出来发现有些case没有考虑到。 参考了答案，发现最快的dp也只能O(n2) 的复杂度来解（为什么？？）
- 基本思路就是dp[i]表示以i个字符结尾的时候是True还是False（注意这里的i是1开始的， 但是也用dp[0], 来表示' '空的字符串），初始化dp[0] = True. 之后依次检索以i结尾的子字符串， 如果dp[j] （0 =< j < i）是真， 而且s[j : i] 在checklist 里面，则dp[i] 为真， 这里是会涵盖到每一种情况的。
python
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
#A BF dp way, O(n2) time, O(n) space
dp = [False for _ in xrange(len(s)+1)]
dp[0] = True #empty string ''
for i in xrange(1, len(s)+1):
for j in xrange(i-1, -1, -1):
if dp[j]:
if s[j : i] in wordDict:
dp[i] = True
break
return dp[len(s)]
