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

qnie11

最大字串问题描述大概就是给定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最长的一个

程序运行结果：



import java.util.HashMap;
import java.util.Map;

/**
* @author HEACK
*
*/
public class CompareStr {
   public static void main(String[] args) {
               
        String str1 = "asdfxfghj5246";
        String str2 = "fghjxasdf6743575246";
        CompareStr cj = new CompareStr();
        String longestStr=cj.getLongestString(str1,str2);
        System.out.println("最长子串有：\n\r"+longestStr);
         int n=longestStr.length();
      
         str1=str1.replaceAll(longestStr, "_");
         str2=str2.replaceAll(longestStr,"_");
        longestStr=cj.getLongestString(str1,str2);
           
        int m=longestStr.length();
         while(m==n){
             System.out.println(longestStr);
             str1=str1.replaceAll(longestStr, "_");
             str2=str2.replaceAll(longestStr,"_");
             longestStr=cj.getLongestString(str1,str2);
              m=longestStr.length();
        }
   }

   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 == str2List) {
             longestStr.append(str1List);
          } 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;
      }
}

}