题解 | #最长公共子串#
代码 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 正确
放弃了上述方法，修改了解题思路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;
}