LeetCode 1092. Shortest Common Supersequence    原题链接    困难

作者： 作者的头像   wzc1995 ,  2019-06-17 11:35:16 ,  所有人可见 ,  阅读 1186

2


题目描述

给出两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。

（如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的_任意位置_），可以得到字符串 S，那么 S 就是 T 的子序列）

样例

输入：str1 = "abac", str2 = "cab"
输出："cabac"
解释：
str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。 
str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。
最终我们给出的答案是满足上述属性的最短字符串。

注意

  • 1 <= str1.length, str2.length <= 1000
  • str1 和 str2 都由小写英文字母组成。

算法

(动态规划) $O(nm)$
  1. 经典的最长公共子序列问题，求出最长公共子序列后，按照动态规划存储的数组来逆推答案串。
  2. 下面介绍最长公共子序列算法：设 $f(i, j)$ 为查看了 str1 的前 $i$ 个字符和 str2 的前 $j$ 个字符后的最长公共子序列。
  3. 初始时 $f(i, 0) = 0, f(0, j) = 0$。转移时，如果 str1[i] == str2[j]，则 $f(i, j) = f(i - 1, j - 1) + 1$；否则 $f(i, j) = \max(f(i - 1, j), f(i, j - 1))$。
  4. 最终答案为 $f(n, m)$。

时间复杂度

  • 动态规划的状态数为 $O(nm)$，转移时间 $O(1)$，故动态规划的时间复杂度为 $O(nm)$。
  • 寻找答案需要 $O(n + m)$ 的时间复杂度，故总时间复杂度为 $O(nm)$。

空间复杂度

  • 需要额外 $O(nm)$ 的空间记录状态，故空间复杂度为 $O(nm)$。

C++ 代码

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        int n = str1.size(), m = str2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
        str1 = " " + str1;
        str2 = " " + str2;

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (str1[i] == str2[j])
                    f[i][j] = f[i - 1][j - 1] + 1;
                else
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }

        string ans;
        int i = n, j = m;
        while (i > 0 || j > 0) {
            if (i == 0) {
                ans += str2[j];
                j--;
            } else if (j == 0) {
                ans += str1[i];
                i--;
            } else {
                if (str1[i] == str2[j]) {
                    ans += str1[i];
                    i--;
                    j--;
                } else {
                    if (f[i][j] == f[i - 1][j]) {
                        ans += str1[i];
                        i--;
                    } else {
                        ans += str2[j];
                        j--;
                    }
                }
            }
        }

        reverse(ans.begin(), ans.end());
        return ans;
    }
};

2 评论

用户头像
JasonSun   2019-12-22 22:32         踩      回复

相似的解法， slightly different flavor.

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:
  string shortestCommonSupersequence(string str1, string str2) {
    const int n1 = size(str1);
    const int n2 = size(str2);
    const int maxn = 1000;

    auto f = rec([&, memo = array<array<optional<int>, maxn>, maxn> {}](auto &&f, int i, int j) mutable -> int {
      if (memo[i][j]) return *memo[i][j];
      return *(memo[i][j] = [&] {
        if (i == 0)
          return j + 1 + (str2.substr(0, j + 1).find(str1[i]) != -1 ? 0 : 1);
        else if (j == 0)
          return i + 1 + (str1.substr(0, i + 1).find(str2[j]) != -1 ? 0 : 1);
        else if (str1[i] == str2[j])
          return 1 + f(i - 1, j - 1);
        else if (str1[i] != str2[j])
          return std::min(f(i - 1, j), f(i, j - 1)) + 1;
        else throw std::domain_error("unmatched case");
      }());
    });

    auto backtrace = [&] {
      vector<char> trace;
      auto path = rec([&](auto&& path, int i, int j) -> void {
        if (i == 0) {
          if (str2.substr(0, j + 1).find(str1[i]) == -1) trace.emplace_back(str1[i]);
          std::copy(rend(str2) - 1 - j, rend(str2), std::back_inserter(trace));
        }
        else if (j == 0) {
          if (str1.substr(0, i + 1).find(str2[j]) == -1) trace.emplace_back(str2[j]);
          std::copy(rend(str1) - 1 - i, rend(str1), std::back_inserter(trace));
        }
        else if (str1[i] == str2[j])         (trace.emplace_back(str1[i]), path(i - 1, j - 1));
        else if (1 + f(i - 1, j) == f(i, j)) (trace.emplace_back(str1[i]), path(i - 1, j));
        else if (1 + f(i, j - 1) == f(i, j)) (trace.emplace_back(str2[j]), path(i, j - 1));
        else throw std::domain_error("unmatched error");
      });
      return path(n1 - 1, n2 - 1), std::string(trace.rbegin(), trace.rend());
    };

    return backtrace();
  }
};
用户头像
JasonSun   2019-12-22 22:36         踩      回复

C++ 有尾递归优化， 所以这两段递归compile出来应该在只用fix number of stack frame， 大体机器码就是跟while loop 和 打表差不多。