题目描述:
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".
题目大意:
给定一个字符串s和一个单词的字典dict,判断s是否可以分隔成由一个或多个字典中的单词组成的序列。
例如,给定s = "leetcode", dict = ["leet", "code"]
返回true,因为"leetcode"可以分隔成"leet code"。
解题思路:
BFS(广度优先搜索)
将当前单词拆分为前后两半,若前缀可以在字典dict中找到,则将后缀加入队列。
Python代码:
class Solution:
# @param s, a string
# @param wordDict, a set<string>
# @return a boolean
def wordBreak(self, s, wordDict):
queue = [s]
visitSet = set([s])
while queue:
front = queue.pop(0)
if front in wordDict:
return True
prefix = ''
for c in front:
prefix += c
suffix = front[len(prefix):]
if prefix in wordDict and suffix not in visitSet:
queue.append(suffix)
visitSet.add(suffix)
return False
另附一段简练的代码,参考LeetCode Discuss
链接地址:https://leetcode.com/discuss/41411/4-lines-in-python
Python代码:
class Solution:
# @param s, a string
# @param wordDict, a set<string>
# @return a boolean
def wordBreak(self, s, words):
ok = [True]
for i in range(1, len(s)+1):
ok += any(ok[j] and s[j:i] in words for j in range(i)),
return ok[-1]
本文链接:http://bookshadow.com/weblog/2015/07/17/leetcode-word-break/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。