Go语言视频零基础入门到精通

javalearner

最大字串问题描述大概就是给定2个字符串，找出他们两个共有的最长子字符串。比如一个是"tabcfg"另外一个"abckj"那么最大子串就是"abc".
     动态规划算法最重要的就是分解问题，找出递归。说一下我的思考思路，首先拿到2个字符串，如何找到最长子串呢？
1.假设他们(字符串a,b)的头字母不相同的话，那么分别去掉首字母比较，也就是说用a.subString(1)和b比较，用b.subString(1)和a比较，最长子字符串没变吧？答案是肯定的。ok递归出现了，结束条件就是有一个字符串变空，返回值就是a和b的最长子串。

2.假设他们头字母相同，那么一直比较下去，直到两者的第n个字母不相同，然后把前n-1个字母存为子字符串c,把a.subString(1)和b的比较结果记为d,b.subString(1)和a比较结果记为e,那么返回c，d和e最长的一个

程序运行结果：

1. import java.util.HashMap;
   
2. import java.util.Map;
   
3. 
   
4. /**
   
5. * @author HEACK
   
6. *
   
7. */
   
8. public class CompareStr {
   
9.    public static void main(String[] args) {
   
10.                
    
11.         String str1 = "asdfxfghj5246";
    
12.         String str2 = "fghjxasdf6743575246";
    
13.         CompareStr cj = new CompareStr();
    
14.         String longestStr=cj.getLongestString(str1,str2);
    
15.         System.out.println("最长子串有：
16. 
    "+longestStr);
    
17.          int n=longestStr.length();
    
18.       
    
19.          str1=str1.replaceAll(longestStr, "_");
    
20.          str2=str2.replaceAll(longestStr,"_");
    
21.         longestStr=cj.getLongestString(str1,str2);
    
22.            
    
23.         int m=longestStr.length();
    
24.          while(m==n){
    
25.              System.out.println(longestStr);
    
26.              str1=str1.replaceAll(longestStr, "_");
    
27.              str2=str2.replaceAll(longestStr,"_");
    
28.              longestStr=cj.getLongestString(str1,str2);
    
29.               m=longestStr.length();
    
30.         }
    
31.    }
    
32. 
    
33.    private boolean isEmpty(String str) {
    
34.                 return str == null || str.trim().length() == 0;
    
35.         }
    
36.   private Map map = new HashMap();
    
37. 
    
38.   private String getLongestString(String str1, String str2) {
    
39.      if (isEmpty(str1) || isEmpty(str2)) {
    
40.                         return "";
    
41.       }
    
42.      StringBuffer key = new StringBuffer();
    
43.      key.append(str1).append("&&").append(str2);
    
44.      if (map.containsKey(key.toString())) {
    
45.           return (String)map.get(key.toString());
    
46.       }
    
47.       StringBuffer longestStr = new StringBuffer();
    
48.       char[] str1List = str1.toCharArray();
    
49.       char[] str2List = str2.toCharArray();
    
50.       int i = 0;
    
51.       for (i = 0; i < str1List.length && i < str2List.length; i++) {
    
52.          if (str1List[i] == str2List[i]) {
    
53.              longestStr.append(str1List[i]);
    
54.           } else {
    
55.              break;
    
56.           }
    
57.       }
    
58.       String subStr1 = str1.substring(i);
    
59.       String subStr2 = str2.substring(i);
    
60.       if (i == 0) {
    
61.        String retStr1 = getLongestString(subStr1.substring(1), subStr2);
    
62.        String retStr2 = getLongestString(subStr1, subStr2.substring(1));
    
63.        String returnStr = retStr1.length() >= retStr2.length() ? retStr1 : retStr2;
    
64.         map.put(key.toString(), returnStr);
    
65.        return returnStr;
    
66.       } else {
    
67.        String retStr1 = getLongestString(str1.substring(1), str2);
    
68.        String retStr2 = getLongestString(str1, str2.substring(1));
    
69.        String retStr = retStr1.length() > retStr2.length() ? retStr1 : retStr2;
    
70.        String returnStr = retStr.length() >= longestStr.toString().length() ? retStr : longestStr.toString();
    
71.        map.put(key.toString(), returnStr);
    
72.        return returnStr;
    
73.       }
    
74. }
    
75. 
    
76. }

复制代码

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/24/000526562.zip