字符串只不过是字符的组合，处理字符串是程序员生活中常见的一部分。
与字符串相关的问题在面试中经常被问到。无论是寻找下一个排列还是寻找最长的公共子序列，你都会在面试中发现一个或多个与字符串相关的问题。
在这里，我们将讨论一个常见问题，即打印最长公共子序列。
在这里您必须注意的一件事是，在查找公共子序列和打印最长公共子序列方面存在差异。
问题陈述
您将得到两个字符串，您必须确定给定字符串之间的最长公共子序列。另外，请记住，字符串只能按相同的顺序排列。
字符串的子序列定义为可以从字符串派生而无需更改字符串的任何元素的字符序列。其他剩余字符串的顺序应该相同。
要理解这个问题，请考虑以下示例：
给你两个字符串：字符串 1：AECFDEF 和字符串 2：BACGDBF
现在，程序的输出将是 ACDF，因为在所有其他子序列中，它是最大的一个。
所以，现在你可能已经知道什么是字符串的子序列了。让我们继续讨论如何在两个字符串中找到最长的公共子序列。
如何在两个字符串中找到最长的公共子序列
要找到最长的公共子序列，可以使用两种方法。他们是 –
- 简单的方法
- 动态规划
简单的方法
要找到最长的公共子序列，遵循一个简单的方法，您需要检查字符串 1 的每个子序列并确定它是否是字符串 2 的子序列。
考虑S1和S2子序列的长度分别为m和n。
在这里，该函数将接受两个序列作为其参数，并将使用两个迭代器遍历该序列。
此外，在此算法中，当任何长度无效时，事情会变得很棘手。
然后，您必须检查两个迭代器中的当前元素，如果它们相等，则需要将其包含在最大的公共子序列中。此外，递归调用每个字符串中的前一个元素。
但是，如果迭代器不相等，您将无法获得 LCS 并在其中包含任何现有元素。
复杂性分析
– 时间复杂度：此方法的时间复杂度为 O(2^(m+n))。这里，m 和 n 是给定字符串的长度。
– 空间复杂度：由于该算法没有使用额外的空间，因此该方法的空间复杂度计算为 O(1)。
动态规划
在使用简单方法时，有时会多次分析相同的子问题，或者某些问题可能会重叠。在这种情况下，使用有效的解决方案。
为了克服简单方法的所有缺点，动态规划用于找到最长的公共子序列。
该过程包括以下步骤：
首先，您需要先创建一个尺寸为 (m+1)*(n+1) 的表格。这里，m 和 n 是给定字符串的大小。现在，您必须在表格的第一列和第一行中设置 0。
在此之后，您需要按照以下步骤填充您创建的表格的其他单元格：
如果相应行和列中存在的字符相同，则必须将与元素对角线的当前单元格加 1。此外，将箭头指向对角单元格。
如果字符不同，我们需要用与前一个相同的值填充当前单元格。箭头必须指向具有最大值的单元格。此外，当两个单元格中的值相等时，您可以将箭头指向其中任何一个。
您将不得不重复步骤 2，直到表格完全填满。
现在，最后一列和最后一行将确定所需公共子序列的长度。
此外，要找到最长的公共子序列，您需要从结束元素开始按照箭头的方向。与括号相邻的所有元素都将创建所需的子序列。
关于这些方法，您必须记住的一件事是这些方法将帮助您找到子序列的长度。您将无法打印子序列的实际值。因此，如果您希望打印该值，请查看打印最长公共子序列所需的操作。
如何打印最长的公共子序列
为了打印最长的公共子序列，您需要执行不同的算法。以下是该过程中涉及的所有步骤。
首先，您必须创建 L[m+1][n+1]。
这里，L[m][n] 将包含最长公共子序列的长度。您将需要长度与 LCS+1 相同的字符数组。
然后，您必须从 L[m][n] 开始遍历 2D 数组。对于 L[i][j] 的每个单元格，您需要执行以下步骤。
如果与 L[i][j] 相邻的字符相同，则必须将该字符作为最长公共子序列的一部分。
否则，您将不得不比较 L[i][j-1] 和 L[i-1][j] 的值。然后，您将不得不朝着更大的价值方向前进。
结论
字符串的子序列只是存在于主数组中的字符序列。在寻找最长公共子序列时，您可以使用动态规划或简单的递归方法找到它。
但是，在打印最长公共子序列时，您需要遵循的算法是不同的。我们已经向您解释了您必须遵循的完整方法。
