动态规划

字符串

  • 单词拆分

    难度：中等

    给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
    示例 1：
    输入: s = “leetcode”, wordDict = [“leet”, “code”]
    输出: true
    解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

    示例 2：
    输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
    输出: true
    解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。

    示例 3：
    输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
    输出: false

  • 方法一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution:
      def wordBreak(self, s: str, wordDict: List[str]) -> bool:
          ss = set(wordDict)
          n = len(s)
          f = [False] * (n + 10)
          f[0] = True
          for i in range(1, n + 1):
              j = i
              while j >= 1 and not f[i]:
                  sub = s[j - 1:i]
                  if sub in ss:
                      f[i] = f[j - 1]
                  j -= 1
          return f[n]

    解析

    复杂度分析
    时间复杂度：O(n^2) ，其中 n 为字符串 s 的长度。我们一共有 O(n) 个状态需要计算，每次计算需要枚举 O(n) 个分割点，哈希表判断一个字符串是否出现在给定的字符串列表需要 O(1) 的时间，因此总时间复杂度为 O(n^2)。
    空间复杂度：O(n) ，其中 n 为字符串 s 的长度。我们需要 O(n) 的空间存放 dp 值以及哈希表亦需要 O(n) 的空间复杂度，因此总空间复杂度为 O(n)。