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".
python code：
class Solution:
# @param s, a string
# @param wordDict, a set<string>
# @return a boolean
def wordBreak(self, s, wordDict):
if not s or not wordDict:#边界条件处理
return False
d=[0]#这个list用来记录前多少个字符可以匹配到，如[0,2,4,6]，表示前0，2，4，6个字符构成的子串可以成功匹配
for i in range(1,len(wordDict)+1):#检验s，从第一个字符到第一个字符直至第一个字符到最后一个字符的子串是否匹配
for j in range(len(d)-1,-1,-1):#s的前i个字符构成的子串怎样才算匹配？上一个匹配的位置到i构成的子串加上前面某个能匹配的子串后可以
#在wordDict中找到
if s[d[j]:i] in wordDict:
d.append(i)
break
return len(s)==d[-1] #如果长为len（s）的子串能匹配成功，那么return True