本文共 1244 字，大约阅读时间需要 4 分钟。

原文地址：

已知两个小写的字符串。找出这两个字符串排过序后的公共子序列，输出的结果必须是排过序的。

例子：

Input  :  str1 = "pink", str2 = "kite"Output : "ik" 字符串"ik"是最长的有序字符串，它的其中的一个排列是"ik"，而且是"pink"的子序列。另外的一个排列是"ki"，它是"kite"的子序列。Input  : str1 = "working", str2 = "women"Output : "now"Input  : str1 = "geeks" , str2 = "cake"Output : "ek"Input  : str1 = "aaaa" , str2 = "baba"Output : "aa"

这个问题的想法就是对两个字符串中的字符进行计数。

1、计算每个字符串中的字符出现的频率，并将它们分别存储在计数数组中，比如str1存储在count1[]中，str2存储在count2[]中。

2、现在我们已经对26个字母进行了计数。所以遍历count1[]，对于任何一个下标‘i’用结果字符串连接字符‘result’连接min(count1[i], count2[i]) 次字符 (‘a’+i)。

3、因为我们是按照升序遍历的计数矩阵，所以我们最后的字符串中的字符也是排过序的。

// C++ program to find LCS with permutations allowed#include
   
    using namespace std;// Function to calculate longest string// str1     --> first string// str2     --> second string// count1[]  --> hash array to calculate frequency//              of characters in str1// count[2]  --> hash array to calculate frequency//              of characters in str2// result   --> resultant longest string whose// permutations are sub-sequence of given two stringsvoid longestString(string str1, string str2){    int count1[26] = {
  0}, count2[26]= {
  0};    // calculate frequency  of characters    for (int i=0; i
   

输出：

ek

时间复杂度：O(m + n)，在这里m和n分别是两个输入字符串的长度。

转载地址：http://dwhii.baihongyu.com/