LeetCode 1278. Palindrome Partitioning III    原题链接    困难

作者： 作者的头像   wzc1995 ,  2019-12-01 12:00:31 ,  所有人可见 ,  阅读 1531

4


1

题目描述

给你一个由小写字母组成的字符串 s，和一个整数 k。

请你按下面的要求分割字符串：

  • 首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
  • 接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。

请返回以这种方式分割字符串所需修改的最少字符数。

样例

输入：s = "abc", k = 2
输出：1
解释：你可以把字符串分割成 "ab" 和 "c"，并修改 "ab" 中的 1 个字符，将它变成回文串。

输入：s = "aabbc", k = 3
输出：0
解释：你可以把字符串分割成 "aa"、"bb" 和 "c"，它们都是回文串。

输入：s = "leetcode", k = 8
输出：0

限制

  • 1 <= k <= s.length <= 100
  • s 中只含有小写英文字母。

算法

(动态规划) $O(n^3)$
  1. 首先预处理每个区间 [i, j] 变成回文所需要修改的字符数量（暴力计算即可），记为 $g(i, j)$。
  2. 设 $f(i, j)$ 表示前 $i$ 个字符，分为 $j$ 段最少所需要修改的字符数量，有效字符的下标从 1 开始。
  3. 初始时 $f(i, j)$ 为正无穷，$f(0, 0) = 0$。
  4. 转移时，枚举上一次的分隔点 $l$，从 0 到 $i - 1$，这一次转移所产生的新区间为 [l + 1, i]，即 $f(i, j) = \min(f(l, j - 1) + g(l + 1, j)$。
  5. 最终答案为 $f(n, k)$。

时间复杂度

  • 预处理需要 $O(n^3)$ 的时间。
  • 动态规划状态数为 $O(nk)$ 个，每次转移需要 $O(n)$ 的时间。
  • 故总时间复杂度为 $O(n^3)$。

空间复杂度

  • 需要额外 $O(n^2)$ 的空间记录数组 $g$。
  • 动态规划的状态需要 $O(nk)$ 的空间记录。
  • 总空间复杂度为 $O(n^2)$。

C++ 代码

class Solution {
public:
    int calc(string t) {
        int tot = 0;
        for (int i = 0, j = t.length() - 1; i < j; i++, j--)
            if (t[i] != t[j])
                tot++;

        return tot;
    }

    int palindromePartition(string s, int k) {
        const int MAX = 10000;
        int n = s.length();
        vector<vector<int>> f(n + 1, vector<int>(k + 1, MAX));
        vector<vector<int>> g(n + 1, vector<int>(n + 1, MAX));

        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++)
                g[i][j] = calc(s.substr(i - 1, j - i + 1));

        f[0][0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= min(n, k); j++)
                for (int l = 0; l < i; l++)
                    f[i][j] = min(f[i][j], f[l][j - 1] + g[l + 1][i]);

        return f[n][k];
    }
};

2 评论

用户头像
JasonSun   2019-12-19 01:00         踩      回复

递归实现

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };

class Solution {
 public:
  int palindromePartition(string s, int k) {
    const size_t maxn = 100 + 5;
    const int n = size(s);

    auto cost = rec([&, memo = array<array<optional<int>, maxn>, maxn> {}](auto&& cost, int i, int j) mutable -> int {
      if (memo[i][j]) return *memo[i][j];
      return *(memo[i][j] = [&]{
        if (i + 1 == j)
          return s[i] == s[j] ? 0 : 1;
        else if (i == j)
          return 0;
        else if (i + 2 <= j)
          return (s[i] == s[j] ? 0 : 1) + cost(i + 1, j - 1);
        else throw std::domain_error("unmatched case");
      }());
    });

    auto f = rec([&, memo = array<array<optional<int>, maxn>, maxn> {}](auto&&f, int i, int k) mutable -> int {
      if (memo[i][k]) return *memo[i][k];
      return *(memo[i][k] = [&] {
        if (i + 1 == k)
          return 0;
        else if (k == 1)
          return cost(0, i);
        else if (i + 1 > k) {
          int acc = INT_MAX;
          for (int mid = k - 2; mid < i; ++mid) 
            acc = std::min(acc, f(mid, k - 1) + cost(mid + 1, i));
          return acc;
        }
        else throw std::domain_error("unmatched case");
      }());
      });

    return f(n - 1, k);
  }
};
用户头像
JasonSun   2019-12-19 01:02         踩      回复

优化了一下OP的实现， 4ms beat 99%. 不开O2