問題描述
給出兩個字符串抄伍，求出兩個字符串公共字符串的最大長度
例如："acbbsdef","acbesdsd"
最大公共字符串長度為3腻菇；為acb
解題思路
采用一個二維矩陣來記錄中間的結(jié)果。比如"abab"和"aba",如果兩個字符相等槽地，那么此處值等于其左上角元素加1烧栋，入下結(jié)果可知，最長的長度為3苇倡，最長的結(jié)果就是其對角線上的元素aba
| a | b | a | b | |
|---|---|---|---|---|
| a | 1 | 0 | 1 | 0 |
| b | 0 | 2 | 0 | 2 |
| a | 1 | 0 | 3 | 0 |
/**
* 求兩個字符串的最長公共子串
* 矩陣法
*/
public class CommonStringPro {
/**
* 求公共子串
* @param str1
* @param str2
*/
public static int getCommonStr(String str1,String str2){
//將兩個字符串轉(zhuǎn)換成char數(shù)組 便于操作
char chars1[] =str1.toCharArray();
char chars2 []=str2.toCharArray();
//構(gòu)建二維數(shù)組 存儲兩個字符串相同的元素
int res[][]=new int [chars1.length][chars2.length];
//動態(tài)規(guī)劃解決問題 把矩陣兩個字符串相同的元素置為左上角元素值加1
for (int i=0;i<chars1.length;i++){
for (int j=0;j<chars2.length;j++){
if (chars1[i]==chars2[j]){
//第一行的情況 第一列的情況
if (i==0||j==0){
res[i][j]=1;
}else {
res[i][j]=res[i-1][j-1]+1;
}
}else {
//對于其他不相同的元素 表中設(shè)為0
res[i][j]=0;
}
}
}
//得到最長字符串長度
int x=0; int y=0;//記錄最大元素下標(biāo)值
int max=0;
for (int i=0;i<chars1.length;i++){
for (int j=0;j<chars2.length;j++) {
if (res[i][j]>max){
max=res[i][j];
}
}
}
return max;
}
public static void main(String[] args) {
System.out.println(getCommonStr("acbbsdef","acbesdsd"));
//輸出結(jié)果為3
}
}
