Interleaving String

描述

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example, Given: s1 = "aabcc", s2 = "dbbca",

When s3 = "aadbbcbcac", return true.

When s3 = "aadbbbaccc", return false.

分析

设状态f[i][j]，表示s1[0,i]和s2[0,j]，匹配s3[0, i+j]。如果s1的最后一个字符等于s3的最后一个字符，则f[i][j]=f[i-1][j]；如果s2的最后一个字符等于s3的最后一个字符，则f[i][j]=f[i][j-1]。因此状态转移方程如下：

  1. f[i][j] = (s1[i - 1] == s3 [i + j - 1] && f[i - 1][j])
  2.        || (s2[j - 1] == s3 [i + j - 1] && f[i][j - 1]);

递归

  1. // Interleaving String
  2. // 递归，会超时，仅用来帮助理解
  3. class Solution {
  4. public:
  5.     bool isInterleave(const string& s1, const string& s2, const string& s3) {
  6.         if (s3.length() != s1.length() + s2.length())
  7.             return false;
  9.         return isInterleave(begin(s1), end(s1), begin(s2), end(s2),
  10.                 begin(s3), end(s3));
  11.     }
  13.     template
  14.     bool isInterleave(InIt first1, InIt last1, InIt first2, InIt last2,
  15.             InIt first3, InIt last3) {
  16.         if (first3 == last3)
  17.             return first1 == last1 && first2 == last2;
  19.         return (*first1 == *first3
  20.                 && isInterleave(next(first1), last1, first2, last2,
  21.                         next(first3), last3))
  22.                 || (*first2 == *first3
  23.                         && isInterleave(first1, last1, next(first2), last2,
  24.                                 next(first3), last3));
  25.     }
  26. };

动规

  1. // Interleaving String
  2. // 二维动规，时间复杂度O(n^2)，空间复杂度O(n^2)
  3. class Solution {
  4. public:
  5.     bool isInterleave(const string& s1, const string& s2, const string& s3) {
  6.         if (s3.length() != s1.length() + s2.length())
  7.             return false;
  9.         vector> f(s1.length() + 1,
  10.                 vector(s2.length() + 1, true));
  12.         for (size_t i = 1; i

动规+滚动数组

  1. // Interleaving String
  2. // 二维动规+滚动数组，时间复杂度O(n^2)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     bool isInterleave(const string& s1, const string& s2, const string& s3) {
  6.         if (s1.length() + s2.length() != s3.length())
  7.             return false;
  9.         if (s1.length() < s2.length())
  10.             return isInterleave(s2, s1, s3);
  12.         vector f(s2.length() + 1, true);
  14.         for (size_t i = 1; i

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/dp/interleaving-string.html