之前写过一篇博客是关于最长公共子序列的博客算法27:最长公共子序列(力扣1143题)——样本模型(4)_样本模型无效的条件-CSDN博客
子序列是可以删除某些字符达到的。
比如:字符串1为 a1b2c3. 字符串2为 aqvb2dcm3.
最长公共子序列就是: ab2c3.
最长公共子串就是 : b2. 公共子串,是不可以删除的
给你两个字符串,找出最长公共字符串:
这一题就是找规律,假设 两个字符串分别为 delete 和 leet。
我们发现,只要是两个字符相等,就依赖左上方的值 和 当前列的值,组成一个新的公共子串。
对不对呢?
继续假设 sea 和 eat,公共子串应该为 ea
那如果没有公共子串呢?
代码:
package code04.动态规划专项训练03;
public class LeetCode712_找公共子串2 {
public String maxStr(String s1, String s2) {
//边界值
if (s1 == null || s2 == null || s1.isEmpty() || s2.isEmpty()) {
return "";
}
if (s1.length() == 1 && s2.length() == 1) {
return s1.charAt(0) == s2.charAt(0) ? String.valueOf(s1.charAt(0)) : "";
}
char[] s1Str = s1.toCharArray();
char[] s2Str = s2.toCharArray();
String[][] dp = new String[s1.length()][s2.length()];
String result = "";
//s1做行,s2做列
//第一行
for (int i = 0; i < s2.length(); i++) {
if (s1Str[0] == s2Str[i]) {
dp[0][i] = String.valueOf(s1Str[0]);
if (!"".equals(dp[0][i])) {
result = String.valueOf(dp[0][i]);
}
}
else {
dp[0][i] = "";
}
}
//第一列
for (int i = 0; i < s1.length(); i++) {
if (s1Str[i] == s2Str[0]) {
dp[i][0] = String.valueOf(s2Str[0]);
if (!"".equals(String.valueOf(dp[0][i]))) {
result = String.valueOf(dp[0][i]);
}
}
else {
dp[i][0] = "";
}
}
for (int index1 = 1; index1 < s1Str.length; index1++) {
for (int index2 = 1; index2 < s2Str.length; index2++) {
//
if (s1Str[index1] == s2Str[index2]) {
dp[index1][index2] = dp[index1 - 1][index2 - 1] + s1Str[index1];
}
else{
dp[index1][index2] = "";
}
if (dp[index1][index2].length() > result.length()) {
result = dp[index1][index2];
}
}
}
return result;
}
public static void main(String[] args) {
/* String s1 = "eab";
String s2 = "eac";*/
/* String s1 = "leet";
String s2 = "delete";*/
String s1 = "a1b2c3";
String s2 = "aqvb2dcm3";
LeetCode712_找公共子串2 ss = new LeetCode712_找公共子串2();
System.out.println(ss.maxStr(s1, s2));
}
}