Word Break

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Example

Given s = "lintcode", dict = ["lint", "code"].

Return true because "lintcode" can be break as "lint code".

Solution

f[i - j] and s[i - j:i] 表示从后面倒数第一个，第二个第三个，依次从后往前去比较而F[j] 从前比较，由于j表示前j个这时后面的s[j-1+1: i-1+ 1] so S[i-j: i]

state: f[i]表示“前i”个字符能否被完美切分 function: f[i] = OR{f[j]}, j < i, j+1 ~ i是一个词典中的单词initialize: f[0] = true answer: f[s.length()]

class Solution:
    # @param s: A string s
    # @param dict: A dictionary of words dict
    def wordBreak(self, s, dict):
        if len(dict) == 0:
            return len(s) == 0

        n = len(s)
        f = [False] * (n + 1)
        f[0] = True

        maxLength = max([len(w) for w in dict])

        for i in range(1, n + 1):
            for j in range(1, min(i, maxLength) + 1):
                if f[i - j] and s[i - j:i] in dict:
                    f[i] = True
                    break

        return f[n]