[LeetCode]题解（python）：139-Word Break

题目来源：

　　https://leetcode.com/problems/word-break/

题意分析：

　　给定一个字符串s和一个字典dict，判断s是不是由字典dict里面的元素组成的。

题目思路：

　　这里可以用动态规划的思想。首先用一个tq[] 存储所有s[:i] 可以由dict组成的下标。如果存在s[tq[i] : j + 1] in dict，那么将j + 1加入tq，如果size在tq里面，那么返回True，否者返回False。

代码（python）：

class Solution(object):

    def wordBreak(self, s, wordDict):

        """

        :type s: str

        :type wordDict: Set[str]

        :rtype: bool

        """

        size = len(s)

        if size == 0:

            return True

        tq = [0]

        i = 0

        while i < size:

            j,nsize = 0,len(tq)

            while j < nsize:

                if s[tq[j]:i+1] in wordDict:

                    if i + 1== size:

                        return True

                    tq.append(i+1)

                    break

                j += 1

            i += 1

        return False

巴特西

[LeetCode]题解（python）：139-Word Break

最新文章

热门文章