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".

解题方法

只求最终是否能够的状态，并且前后子问题都有联系，可以往DP方向想。

1. state

canBreak[i]表示前i个字符是否能够做word break

1. function

canBreak[i] = True if canBreak[j] and (s[j:i] in wordDict) for j < i

1. result

canBreak[len(s)]

Solution

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """
        if not wordDict:
            return False

        length = len(s)

        canBreak = [False for i in range(length+1)]
        canBreak[0] = True

        for i in range(1, length+1):
            for j in range(i):
                if canBreak[i]:
                    continue
                if (s[j:i] in wordDict) and canBreak[j]:
                    canBreak[i] = True

        return canBreak[length]

Reference

• word break