题目描述：

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/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码