每天一道算法题：求两个字符串的最长公共子序列

分手后的思念是犯贱 2022-10-28 13:27 124阅读 0赞

## 最长子序列（LCS） ##

公共子序列是在整个字符串中只要按照顺序可以不用连续的，但是公共子串是指必须连续的字符串，举个例子:

ABCBDAB
    BDCABA

最长公共子序列是 : BCBA  
最长公共字串是 : AB

## 递归思路 ##

先将两个字符串的第一个字符进行比较

*  **如果第一个字符相同**：再将剩下的字符进行比较
 *  **如果第一个字符不相同**：与之对应有两种情况

1.  将截取了一个字符的串1与完整的串2进行比较
2.  将截取了一个字符的串2与完整的串1进行比较
3.  根据这两种情况的返回结果进行比较，大的那个就是**LCS**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70]  
**代码实现：**

public static int getLCS(String s1,String s2){ 
            //如果其中一个字符串的长度为0，返回0
            if(s1.length()==0||s2.length()==0) return 0;
            //如果第一个字符相等，则说明最长的公共子序列一定有这个字符，故+1
            if(s1.charAt(0)==s2.charAt(0)) return getLCS(s1.substring(1),s2.substring(1))+1;
            //如果第一个字符不相同，那么就有两种情况：
            //1.第一个字符串和从第一个字符开始截取的第二个字符串进行比较
            //2.从第一个字符开始截取的第二个字符串与第一个字符串进行比较
            //然后对这两种情况进行比较，大的那个就是最长的LCS
            else return Math.max(getLCS(s1.substring(1),s2),getLCS(s1,s2.substring(1)));
        }

## 动态规划思路 ##

**分析问题的最优子结构性质：**  
假定有两个字符串，S1 = \{1,5.2.8.9.3.6\}, S2=\{5,6,8,9,3,7\},其最长的公共子序列LCS为\{5,8,9,3\},最长公共子序列为4;

设序列S1=\{x1,x2…,xn\}和S2=\{y1,y2…,ym\}的最长公共子序列为S=\{z1,z2…,zk\}则：

1.  若xn=ym，那么zk=xn=ym，且S\[k-1\]是S1\[n-1\]和S2\[m-1\]的最长公共子序列
2.  若xn!=ym且zk!=xn，则S\[k\]是S1\[n-1\]和S2\[m\]的最长公共子序列；
3.  若xn!=ym且zk!=ym，则S\[k\]是S1\[n\]和S2\[m-1\]的最长公共子序列。

对以上分析，我们可以建立递推公式  
【ps：dp\[i\]\[j\]表示：S1的前i个字符和S2的前j个字符的最长公共子序列的长度】  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70 1]  
**代码实现：**

public static int getLCS2(String s1,String s2){ 
            int len1 = s1.length();
            int len2 = s2.length();
            int c[][] = new int[len1+1][len2+1];
            for (int i = 0; i <= len1; i++) { 
                for( int j = 0; j <= len2; j++) { 
                    if(i == 0 || j == 0) { 
                        c[i][j] = 0;
                    } else if (s1.charAt(i-1) == s2.charAt(j-1)) { 
                        c[i][j] = c[i-1][j-1] + 1;
                    } else { 
                        c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
                    }
                }
            }
            return c[len1][len2];
        }

--------------------

参考资料：

1.  https://www.dazhuanlan.com/2019/12/11/5df10ea0b4ec8/
2.  http://www.cppblog.com/mysileng/archive/2013/05/14/200265.html
3.  https://blog.csdn.net/u012102306/article/details/53184446
4.  https://www.bilibili.com/video/BV1Yp4y1U7Lf/?spm\_id\_from=333.788.recommend\_more\_video.2（视频讲解，强推）  
    ps：每个人的智商没有太大区别，更多的只是思考的角度不同，所以，当我们遇到难题无法理解时，要善于从别人的角度去思考问题！（emmm，就是想给自己找个查了这么多资料才能理解的借口）！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70]: /images/20221024/2243aff9bab14a7aa0ee359377bea9c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70 1]: /images/20221024/9a1f43fa6a254b6d823e04d9e9eb84f2.png