web网站测试/苏州百度推广分公司电话

107. 单词拆分 I

给出一个字符串s和一个词典，判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。

样例

给出

s = "lintcode"

dict = ["lint","code"]

返回 true 因为"lintcode"可以被空格切分成"lint code"

解题思路：

判断字符串是否能否拆分为多个出现在字典里的单词，问题可以转换为字典中的单词是否可以组合成字符串。

对字典进行遍历，如果dicts[i]在字符串中，则将字符串中的该元素删除，继续判断下一个字典元素和 剩余字符。

如果剩余字符出现在字典中，则返回True。如果剩余字符为空，也返回True.

class Solution:"""@param: s: A string@param: dict: A dictionary of words dict@return: A boolean"""def wordBreak(self, s, dicts):# write your code heredicts = list(dicts)if s == '' and len(dicts) == 0:return  Truefor i in range(len(dicts)):tmp = swhile i < len(dicts) and dicts[i] in tmp:tmp = tmp.replace(dicts[i], '')if tmp in dicts:return Truei += 1 if tmp == '':return Truereturn False