题解 | #最长公共子序列#

最长公共子序列

http://www.nowcoder.com/questionTerminal/9ae56e5bdf4f480387df781671db5172

题目描述：

链接：https://www.nowcoder.com/questionTerminal/9ae56e5bdf4f480387df781671db5172?answerType=1&f=discussion

来源：牛客网

我们有两个字符串m和n，如果它们的子串a和b内容相同，则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。

例如字符串“abcfbc”和“abfcab”，其中“abc”同时出现在两个字符串中，因此“abc”是它们的公共子序列。此外，“ab”、“af”等都是它们的字串。

现在给你两个任意字符串（不包含空格），请帮忙计算它们的最长公共子序列的长度。

输入描述:

输入包含多组数据。

每组数据包含两个字符串m和n，它们仅包含字母，并且长度不超过1024。

输出描述:

对应每组输入，输出最长公共子序列的长度。

示例1

输入

abcfbc abfcab
programming contest
abcd mnp

输出

4
2
0

思路讲解：

要求从两个字符串中，找到最长的子序列，这两个子序列不一定是连续的。以题目中这两个字符串举例， abcfbc abfcab ，公共子序列有 a，ab，abc，af ，abcb等，但最长的只有abcb，我们通过肉眼能很容易的看出来，abcb
是符合题意的最长公共子序列，找出这个子序列，我们潜意识的排除了顺序不对的公共项（就是没有把 abcf 和 abfc 视为符合题意的子序列），排除了字符比较时，相同的字符被重复计算的问题，也没有因为中间有间隔，
就把abc 视为最长公共子序列。

但程序中要让它排除这些问题，常规的方法很麻烦而且很难，于是我们采用动规思想，就是让一个字符串中的每一个字符去和另一个字符串中的每一个字符进行比较，如果相同就给次数加一？不，这样就会出现我前面提到的
问题，相同的字符被重复比较，比如 abcfbc 中的字符 a 在与 abfcab 比较时，会被计算两次。那为了避免这个问题，我们就看它们的前一位，在它们前一位的基础上进行加一。具体看下图，再进一步解释。

根据图来继续进行讲解，因为不能两个字符一相等，就给公共子序列个数加一，我们要看它们的前面一个，所以为了在第一个字符进行比较时有所参考，我们给要比较的两个字符串前面加一个空字符，空字符和谁比较都是0，

这里没有问题吧。然后具体讲解这个记录两个字符比较的二维数组（arr[ ][ ]）如何进行。还是以 abfcab   和   abcfbc为例，刚开始用  abfcab 的 a字符和  abcfbc 的每一个字符进行比较，和它里面的a相同，先看它们的前面一位，

都是空，也就是arr[0][0] =0 (初始化后默认为0) ，那么此刻的公共子序列长度为 0+1 =1，然后继续用 a 比较abcfbc 里的 b，不相同，不相同就看 a前面的空字符与 abcfbc 的ab比较结果是0，再看 a与  abcfbc 中b前面的字符

（也就是a）比较结果是1，所以  abfcab 中的a 与 abcfbc 中的b 公共字符串长度应该是1（取两者的最大值），因为abfcab 中的a  与 abcfbc 中的b（其实是ab）确实有一个相同的字符。  abfcab 中的a 继续与 abcfbc 中的

c,f,b,c 比较结果都是1。

然后，abfcab 中的 b 与 abcfbc 每一个字符进行比较，比到b时，看它们前一位也就是arr[1][1] 是1，所以此时的公共子序列长度为 1+1 =2 ，然后继续比较比到  abcfbc 的第二个b时，看它们的前面一个也就是arr[1][4],

结果是1，所以这里的公共子序列是2，而不是3。为什么总要看前一个，因为 abfcab 中b 的前一个是a ，a与 abcfbc整个比较完也确实只有一个相等（这里不要误解，a与 abcbaaa 比较也只有一个相等）。我们通过看前一个，

就能避免重复的问题。所以这样就能得到，大家看着有点头疼的动规规划状态方程，

若str1[ i ] == str2[ j ]，则 arr[ i ][ j ] = max( dp[ i-1 ][ j ], dp[ i ][ j-1 ], dp[ i-1 ][ j-1 ]+1 )

若str1[ i ] != str2[ j ]，则 dp[ i ][ j ] = max( dp[ i-1 ][ j ], dp[ i ][ j-1 ] ) 现在看它，应该好理解多了吧！

代码解释

// write your code here
import java.util.*;
public class Main{
 public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
     while(scan.hasNext()){
         String m = scan.next();
         String n =scan.next();
         int lenM = m.length();
         int lenN = n.length();
                 // 我们需要给字符串前面加空格，便于后面的字符串比较，所以大小设为 lenM+1和lenN+1 
         int[][] arr = new int[lenM+1][lenN+1];
         for(int i=1;i<= lenM;i++){
             for(int j=1;j<= lenN;j++){
                              // 依次比较两个字符串的每一个字符，但要注意是字符串，要用charAt()函数获取每个字符
                 if(m.charAt(i-1)== n.charAt(j-1)){
                           // 这里就是运用上面的状态方程
                     arr[i][j]= arr[i-1][j-1]+1;
                 }else{
                     arr[i][j]=Math.max(arr[i-1][j],arr[i][j-1]);
                 }
             }
         }
               //  最后为什么要打印这个值，有上面图可以看出 比较结果为4 的位置有多个， 这里是因为，只有arr[lenM][lenN]处的数值，才能代表是两个字符串wan'zhen          System.out.println(arr[lenM][lenN]);
         
     }
     
   }   
}