最大字串問題描述大概就是給定2個(gè)字符串，找出他們兩個(gè)共有的最長(zhǎng)字符串。比如一個(gè)是"tabcfg"另外一個(gè)"abckj"那么最大子串就是"abc".
動(dòng)態(tài)規(guī)劃算法最重要的就是分解問題，找出遞歸。說一下我的思考思路，首先拿到2個(gè)字符串，如何找到最長(zhǎng)子串呢？
1.假設(shè)他們(字符串a(chǎn),b)的頭字母不相同的話，那么分別去掉首字母比較，也就是說用a.subString(1)和b比較，用b.subString(1)和a比較，最長(zhǎng)子字符串沒變吧？答案是肯定的。ok遞歸出現(xiàn)了，結(jié)束條件就是有一個(gè)字符串變空，返回值就是a和b的最長(zhǎng)子串。
b.假設(shè)他們頭字母相同，那么一直比較下去，知道兩者的第n個(gè)字母不相同，然后把前n-1個(gè)字母存為子字符串c,把a(bǔ).subString(1)和b返回結(jié)果記為d,b.subString(1)和a返回結(jié)果記為e,那么返回c，d和e最長(zhǎng)的一個(gè)(感謝lexy的評(píng)論，之前確實(shí)遺漏一種情況。不應(yīng)該直接把前面的相同的去掉直接比較的，現(xiàn)在代碼已經(jīng)更新了)。
也許有人說應(yīng)該從后面往前面比較，找到相同的然后一個(gè)個(gè)再往前比，其實(shí)道理都是一樣的，關(guān)鍵要找到分解問題的方法。這里只是拋磚引玉，下面是具體的java實(shí)現(xiàn)。
import java.util.HashMap;
import java.util.Map;
/**
* @author HEACK
*
*/
public class CompareStr {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "abcde1234567abcdefghijk";
String str2 = "abcdefgh12345";
//String str2 = "abc happyies dutcbirthday peter";
CompareStr cj = new CompareStr();
System.out.println(cj.getLongestString(str1,str2));
}
private boolean isEmpty(String str) {
return str == null || str.trim().length() == 0;
}
private Map map = new HashMap();
private String getLongestString(String str1, String str2) {
if (isEmpty(str1) || isEmpty(str2)) {
return "";
}
StringBuffer key = new StringBuffer();
key.append(str1).append("&&").append(str2);
if (map.containsKey(key.toString())) {
return (String)map.get(key.toString());
}
StringBuffer longestStr = new StringBuffer();
char[] str1List = str1.toCharArray();
char[] str2List = str2.toCharArray();
int i = 0;
for (i = 0; i < str1List.length && i < str2List.length; i++) {
if (str1List[i] == str2List[i]) {
longestStr.append(str1List[i]);
} else {
break;
}
}
String subStr1 = str1.substring(i);
String subStr2 = str2.substring(i);
if (i == 0) {
String retStr1 = getLongestString(subStr1.substring(1), subStr2);
String retStr2 = getLongestString(subStr1, subStr2.substring(1));
String returnStr = retStr1.length() >= retStr2.length() ? retStr1 : retStr2;
map.put(key.toString(), returnStr);
return returnStr;
} else {
String retStr1 = getLongestString(str1.substring(1), str2);
String retStr2 = getLongestString(str1, str2.substring(1));
String retStr = retStr1.length() > retStr2.length() ? retStr1
: retStr2;
String returnStr = retStr.length() >= longestStr.toString().length() ? retStr
: longestStr.toString();
map.put(key.toString(), returnStr);
return returnStr;
}
}
}
HashMap用來存儲(chǔ)已經(jīng)計(jì)算過的字符串，用空間換時(shí)間。代碼當(dāng)然還可以優(yōu)化，您也可以一試身手哦。