最大字串問題描述大概就是給定2個字符串，找出他們兩個共有的最長字符串。比如一個是"tabcfg"另外一個"abckj"那么最大子串就是"abc".
動態規劃算法最重要的就是分解問題，找出遞歸。說一下我的思考思路，首先拿到2個字符串，如何找到最長子串呢？
1.假設他們(字符串a,b)的頭字母不相同的話，那么分別去掉首字母比較，也就是說用a.subString(1)和b比較，用b.subString(1)和a比較，最長子字符串沒變吧？答案是肯定的。ok遞歸出現了，結束條件就是有一個字符串變空，返回值就是a和b的最長子串。
b.假設他們頭字母相同，那么一直比較下去，知道兩者的第n個字母不相同，然后把前n-1個字母存為子字符串c,把a.subString(1)和b返回結果記為d,b.subString(1)和a返回結果記為e,那么返回c，d和e最長的一個(感謝lexy的評論，之前確實遺漏一種情況。不應該直接把前面的相同的去掉直接比較的，現在代碼已經更新了)。
也許有人說應該從后面往前面比較，找到相同的然后一個個再往前比，其實道理都是一樣的，關鍵要找到分解問題的方法。這里只是拋磚引玉，下面是具體的java實現。
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用來存儲已經計算過的字符串，用空間換時間。代碼當然還可以優化，您也可以一試身手哦。