Word Break

原题

给出一个字符串s和一个词典，判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。

给出

s = "leetcode"

• dict = ["leet","code"]
  返回 True 因为"leetcode"可以被空格切分成"leet code"
• dict = ["leet","code","3"]
  返回 True
• dict = ["leet","cod","g"]
  返回 False

解题思路

• 1、DP初始化时一般要有个1或者true
• 2、本题属于序列型动态规划 - Sequence DP
• f[i]表示前i个字符能不能被dict完美划分
  判断f[i]，则需要遍历0_{i中是否存在一个j，使得f[j]=true而且j+1}i存在于dict中
• 本题还有一个值得注意的地方，一定要考虑到单词长度是有上限的！，所以每次不需要遍历0_i而是xi(i-x为单词最大长度)

def getMaxLength(self, dict):
      maxLength = 0
      for word in dict:
         maxLength = max(len(word), maxLength)
      return maxLength
      
    def wordBreak(self, s, dict):
        n = len(s)
        if n == 0:
            return True
        if len(dict) == 0 :
            return False

        maxLength = self.getMaxLength(dict)
        f = [False] * (n + 1)  # 前i个字符是否可以被切分
        f[0] = True

        for i in range(1, n + 1):  # 前i个字符，枚举j（j小于i）
            j = 1
            while j <= i and j <= maxLength:
                if f[i - j] == False:
                    j += 1
                    continue
                if s[i - j:i] in dict:
                    f[i] = True
                    break
                j += 1

        return f[n]