动æ€è§„划算法最é‡è¦çš„就是分解问题,扑ևºé€’归。说一下我的æ€è€ƒæ€èµ\åQŒé¦–先拿åˆ?个嗽W¦ä¸²åQŒå¦‚何找到最长å串呢åQ?br />
1.å‡è®¾ä»–们(å—符串a,b)çš„å¤´å—æ¯ä¸ç›¸åŒçš„è¯ï¼Œé‚£ä¹ˆåˆ†åˆ«åŽÀLމ首嗿¯æ¯”较,也就是说用a.subString(1)å’Œb比较åQŒç”¨b.subString(1)å’Œa比较åQŒæœ€é•¿åå—符串没å˜å§åQŸç”案是肯定的。ok递归出现了,¾l“æŸæ¡äšgž®±æ˜¯æœ‰ä¸€ä¸ªå—½W¦ä¸²å˜ç©ºåQŒè¿”回值就是aå’Œb的最长å丌Ӏ?br />
b.å‡è®¾ä»–们头嗿¯ç›¸åŒï¼Œé‚£ä¹ˆä¸€ç›´æ¯”较下去,知é“两者的½W¬nä¸ªå—æ¯ä¸ç›¸åŒåQŒç„¶åŽæŠŠå‰n-1ä¸ªå—æ¯å˜ä¸ºåå—符串c,把a.subString(1)å’Œb˜q”回¾l“æžœè®îCØ“d,b.subString(1)å’Œa˜q”回¾l“æžœè®îCØ“e,那么˜q”回cåQŒdå’Œe最长的一ä¸?感谢lexy的评论,之剼‹®å®žé—æ¼ä¸€¿U情å†üc€‚ä¸åº”该直接把å‰é¢çš„相åŒçš„去掉直接比较的åQŒçŽ°åœ¨ä»£ç å·²¾læ›´æ–îCº†)ã€?br />
也许有äh说应该从åŽé¢å¾€å‰é¢æ¯”较åQŒæ‰¾åˆ°ç›¸åŒçš„ç„¶åŽä¸€ä¸ªä¸ªå†å¾€å‰æ¯”åQŒå…¶å®žé“ç†éƒ½æ˜¯ä¸€æ ïLš„åQŒå…³é”®è¦æ‰‘Öˆ°åˆ†è§£é—®é¢˜çš„æ–¹æ³•ã€‚è¿™é‡Œåªæ˜¯æŠ›ç –å¼•çŽ‰ï¼Œä¸‹é¢æ˜¯å…·ä½“çš„java实现ã€?br />
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用æ¥å˜å‚¨å·²ç»è®¡ç®—˜q‡çš„å—符ä¸ÔŒ¼Œç”¨ç©ºé—´æ¢æ—‰™—´ã€‚代ç 当然还å¯ä»¥ä¼˜åŒ–åQŒæ‚¨ä¹Ÿå¯ä»¥ä¸€è¯•èín手哦ã€?br />

]]>