题解 | #最长公共子串#

代码 1.0 错误

list转string时总是出错

package DP;
import java.util.ArrayList;
//最长公共字串
public class LCS_ {
    public static void main(String[] args) {
        String str1="1AB2345CD";
        String str2="12345EF";
        Solution_lcs solution_lcs = new Solution_lcs();
        String str=solution_lcs.LCS(str1,str2);
        System.out.println(str);

    }
}
class Solution_lcs{
    public String LCS (String str1, String str2){
        String long_="";
        String short_="";
        ArrayList res=new ArrayList();
        ArrayList res1=new ArrayList();//res1 为内循环获得的最长公共字串
        ArrayList res2=new ArrayList();//res2 为外循环获得的最长公共字串
        //object[] objects = new object[]{};
        if (str1.length()>=str2.length()){
            long_=str1;
            short_=str2;
        }
        else{
            long_=str2;
            short_=str1;
        }
        for (int i = 0; i < long_.length(); i++) {//外循环头
            int x=i;
            for (int j = 0; j < short_.length(); j++) {//内循环头
                int y=j;
                if (long_.charAt(x)==short_.charAt(j)){
                    res.add(long_.charAt(x));
                    x++;
                }
                else {
                    x=i;
                    j=y;
                    if (!(res.isEmpty())){//结果不为空
                        //res1=res;//res1存放较长字符串
                        if (res.size()>=res1.size()){
                            //res1=res;
                            res1.addAll(res);
                        }
//                        else{
//                            res1=res1;
//                        }
                        res.clear();//清空
                    }
                    //continue;
                }

            }//内循环尾
            if (!(res1.isEmpty())){//res1不为空
                if (res1.size()>=res2.size()){//res2存放较长字符串
                    //res2=res1;
                    res2.addAll(res1);
                }
//                else{
//                    res2=res2;
//                }
                res1.clear();
            }

        }//外循环尾
        //问题一 头======================================================
        //面临的问题1：目标字符串存放在list中
        // 如何将list转化为字符串/list转化为字符数组再转化为字符串
        // 很有必要复习集合
        //String[] str = res2.toArray(new String[res2.size()]);//报错
        //String[] str = ( String[])res2.toArray(new String[res2.size()]);
        String str=String.join(" ",res2);
        //问题一 尾======================================================



        return str;//返回结果
    }
}

代码 2.0 错误

1、弃用list ，核心变量均使用string，解决了上个版本出现的问题，代入示例{str1="1AB2345CD "str2="12345EF"}可以出结果

String str1=new String("1AB2345CD");
String str2=new String("12345EF");

2、str1=“222”,str2="222"时会出错

String str1=new String("22222");
String str2=new String("22222");

逻辑错误：第一次外循环时便找到了最大字串（此时应该退出外循环），但是该系统继续进行第二次外循环。

package DP;
import java.util.ArrayList;
import java.util.Scanner;

//最长公共字串  2.0 将list换做string
public class LCS_ {
    public static void main(String[] args) {
        String str1=new String("22222");//"1AB2345CD"//123qw
        String str2=new String("22222");//"12345EF"//qfq13123
        Scanner scanner = new Scanner(System.in);
        Solution_lcs solution_lcs = new Solution_lcs();
        String str=solution_lcs.LCS(str1,str2);
        System.out.println(str);

    }
}
class Solution_lcs{
    public String LCS (String str1, String str2){
        String long_="";
        String short_="";
        String res=new String("");
        String res1=new String("");//res1 为内循环获得的最长公共字串
        String res2=new String("");//res2 为外循环获得的最长公共字串
        if (str1.length()>=str2.length()){
            long_=str1;
            short_=str2;
        }
        else{
            long_=str2;
            short_=str1;
        }
        for (int i = 0; i < long_.length(); i++) {//外循环头
            int x=i;
            for (int j = 0; j < short_.length(); j++) {//内循环头
                int y=j;
                if (long_.charAt(x)==short_.charAt(j)){
                    //res.add(long_.charAt(x));
                    res=res+long_.charAt(x);
                    x++;
                }
                else {
                    x=i;
                    j=y;
                    if (!(res.isEmpty())){//结果不为空
                        //res1=res;//res1存放较长字符串
                        if (res.length()>=res1.length()){//res.size()>=res1.size()
                            //res1.addAll(res);
                            res1=res;
                        }
                        res="";//res=null 会报错！！！！
                    }
                  
                }

            }//内循环尾
            if (!(res1.isEmpty())){//res1不为空
                if (res1.length()>=res2.length()){//res2存放较长字符串//res1.size()>=res2.size()
                    res2=res1;
                }
                //res1.clear();
                res1="";//res1=null 会报错！！！！
            }

        }//外循环尾
        return res2;//返回结果
    }
}

代码 3.0 正确

放弃了上述方法，修改了解题思路

参考博客：最长公共子串 - 动力节点在线的文章 - 知乎 https://zhuanlan.zhihu.com/p/268342434

public String LCS (String str1, String str2){
        int max_row=0;
        int max_column=0;
        int max_num=0;
        String res="";
        //第一步 生成dp[][]
        //第一步检测：dp数组是否正确
        int dp[][]=new int[str1.length()][str2.length()];
        //第0行与第0列的定义
        for (int i = 0; i < str2.length(); i++) {
            if (str1.charAt(0)==str2.charAt(i)){
                dp[0][i]=1;
            }
        }
        for (int i = 1; i < str1.length(); i++) {
            if (str2.charAt(0)==str1.charAt(i)){
                dp[i][0]=1;
            }
        }
        for (int i = 1; i <str1.length() ; i++) {
            for (int j = 1; j < str2.length(); j++) {
                if (str1.charAt(i)==str2.charAt(j)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j]=0;
                }
            }
        }
        //第二步 找出dp的最大值以及最大值的坐标
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                max_num=Math.max(max_num,dp[i][j]);
                if (max_num==dp[i][j]){
                    max_row=i;
                    max_column=j;
                }
            }
        }
        //第三步 获取字串 (row,column) num
        char res1[]=new char[max_num];
        int index=0;
        for (int i = max_row+1-max_num; i <=max_row; i++) {
            //System.out.print(str1.charAt(i));
            res1[index]=str1.charAt(i);
            index++;
        }
        res=new String(res1);
        return res;
    }