3.5 最长公共子序列(LCS)
前言:图片是博主自己画的,转载请注明出处哦
3.5.1 问题描述
最长公共子序列(Longest Common Subseuence,LCS)问题:给定两个字符串,求解它们的最长公共子序列的长度,其中子序列是指:它是由原字符串在不改变字符的相对顺序的情况下,删除某些字符(也可以不删除任何字符)后组成的新字符串。
3.5.2 算法思路
简单地说,我们要填出下面这张表。
我们的目标是求出ABCBDAB和BDCABA的最长公共子序列。根据动态规划的原则,问题分阶段,那么最开始,我们可以看成求A和B、和BD…和BDCABA的最长公共子序列,这样就填出了第一行的值。
然后同样的道理,把第一列也填了。
这相当于基础工作,现在开始填写第二行。
归纳为:
元素相同,则把左上角的值+1填入元素不同,则把相邻的上边和左边,这两格中最大的那一个数填入。
按照同样的道理,我们可以把整张表填完。这张表最右下角的值,就是最长公共子序列的长度
现在来求解最长公共子序列,因为最长公共子序列不唯一,我们这里就只求出一条路径
按照这样的原理,我们找出了一条路径。
根据填表原理,我们可以容易地看出一条最长公共子序列BCBA。当然,你也可以直接记忆为,谁往左上角走,就选谁,以及最后一个元素必须选,这样选中的就是最长公共子序列
3.5.3 表格法代码实现
public static String getLCSByTabulation(String str1, String str2){int row = str1.length();int col = str2.length();int [][] board =new int[row][col];board[0][0] = (str1.charAt(0)==str2.charAt(0))?1:0;/*核心代码*/for(int i=1;i<row;i++){//初始化第一列board[i][0] = (str1.charAt(i)==str2.charAt(0)|| board[i-1][0]==1)?1:0;}for (int j=1;j<col;j++){//初始化第一行board[0][j] = (str1.charAt(0)==str2.charAt(j)|| board[0][j-1]==1)?1:0;}for(int i=1;i<row;i++){for(int j=1;j<col;j++){if(str1.charAt(i)==str2.charAt(j)){//如果字符相同board[i][j]=board[i-1][j-1]+1;//等于左上角值+1}else{//字符不同board[i][j]=Math.max(board[i-1][j],board[i][j-1]);//继承上面或左边一个的最大值}}}int i=row-1,j=col-1;String lcs="";while(i!=0&&j!=0){/*核心代码*/if(board[i][j]==board[i-1][j])//值和左边一格相同 i--;else if(board[i][j]==board[i][j-1])//值和上边一格相同 j--;else{//值来自左上角一格+1lcs = str1.charAt(i)+lcs;//这个元素是LCS的元素i--;j--;}}lcs=str1.charAt(i)+lcs;//到头啦,加上最后一个元素return lcs;}
3.5.4 算法复杂度
算法复杂度:(mn)