1

我现在一直在研究动态编程，我在一个网站上遇到了一个代码。问题是编写一个函数来检查 C 是否是 A 和 B 的交错。如果 C 包含 A 和 B 的所有字符并且保留单个字符串中所有字符的顺序，则称 C 是交错 A 和 B。我是什么不明白二维矩阵中的值是如何填充的？

需要帮助:) 这是链接 http://www.geeksforgeeks.org/check-whether-a-given-string-is-an-interleaving-of-two-other-given-strings-set-2/

// an interleaving of A and B, otherwise false.
bool isInterleaved(char* A, char* B, char* C)
{
  // Find lengths of the two strings
  int M = strlen(A), N = strlen(B);

  // Let us create a 2D table to store solutions of
  // subproblems.  C[i][j] will be true if C[0..i+j-1]
  // is an interleaving of A[0..i-1] and B[0..j-1].
  bool IL[M + 1][N + 1];

  memset(IL, 0, sizeof(IL)); // Initialize all values as false.

  // C can be an interleaving of A and B only of sum
  // of lengths of A & B is equal to length of C.
  if ((M + N) != strlen(C))
    return false;

  // Process all characters of A and B
  for (int i = 0; i <= M; ++i)
  {
    for (int j = 0; j <= N; ++j)
    {
      // two empty strings have an empty string
      // as interleaving
      if (i == 0 && j == 0)
        IL[i][j] = true;

      // A is empty
      else if (i == 0 && B[j - 1] == C[j - 1])
        IL[i][j] = IL[i][j - 1];

      // B is empty
      else if (j == 0 && A[i - 1] == C[i - 1])
        IL[i][j] = IL[i - 1][j];

      // Current character of C matches with current character of A,
      // but doesn't match with current character of B
      else if (A[i - 1] == C[i + j - 1] && B[j - 1] != C[i + j - 1])
        IL[i][j] = IL[i - 1][j];

      // Current character of C matches with current character of B,
      // but doesn't match with current character of A
      else if (A[i - 1] != C[i + j - 1] && B[j - 1] == C[i + j - 1])
        IL[i][j] = IL[i][j - 1];

      // Current character of C matches with that of both A and B
      else if (A[i - 1] == C[i + j - 1] && B[j - 1] == C[i + j - 1])
        IL[i][j] = (IL[i - 1][j] || IL[i][j - 1]);
    }
  }

  return IL[M][N];
}

void test(char *A, char *B, char *C)
{
  if (isInterleaved(A, B, C))
    cout << C << " is interleaved of " << A << " and " << B << endl;
  else
    cout << C << " is not interleaved of " << A << " and " << B << endl;
}

// Driver program to test above functions
int main()
{
  test("XXY", "XXZ", "XXZXXXY");
}
4

1 回答 1

2

动态规划重用子问题的结果来解决问题。子问题是问题的较小版本。一个表通常用于存储子问题的结果。

该表的索引是特定于应用程序的；在这种情况下，它们在评论中进行了描述：

// Let us create a 2D table to store solutions of
// subproblems.  IL[i][j] will be true if C[0..i+j-1]
// is an interleaving of A[0..i-1] and B[0..j-1].

（我修正了一个错误，C[i][j]应该IL[i][j]在原始来源中）。

子问题确定 和 的子串是否A是BC 的子串的交错。 IL 数组中的索引确定 和 的子串的A长度B（第三个子串的长度隐含在其他两个子串的长度中）。

例如：

  • IL[0][0]是true，因为“”（空字符串）和“”交错形成“”。
  • IL[0][*]也是true，因为 "" 和WHATEVERinterleave 形成WHATEVER（这里的*意思是“任何东西”）。
  • IL[*][0]也是true，出于与上述类似的原因。
  • IL[i][j]是通过比较当前字符in和当前字符 inC来计算的（查看源代码以确定我所说的“当前”是什么意思） AB
    • 如果两者都不匹配，则您知道这不是C交错，因为它包含意外字符。因此，。IL[i][j] = false
    • 如果匹配A，那么您还需要检查前面的字符是否也正确交错。这就是动态编程部分的用武之地——您不需要实际查看所有这些字符来检查它们，因为您在以前的迭代中已经这样做了。检查的结果（这也是您应该返回的最终结果）存储在IL表中，更具体地说，存储在IL[i-1][j]. 因此，IL[i][j] = IL[i-1][j]。
    • 如果匹配B，则执行与上述相同的操作，除了查看IL[i][j-1]。

如果您无法理解动态编程解决方案，我建议您通过网站上的递归解决方案手动工作。最终，你会意识到你在重复许多比较。您可以通过在第一次进行比较时存储比较结果，然后在以后的情况下重新使用该结果来避免这种重复。

于 2013-09-20T04:55:25.873 回答