题解 | #最长公共子串#

循环从1中取字符组成字符串，判断2中是否包含该子串，若包含则继续取，直到取到不包含的字符为止，与最大子串判断长度进行替换

import java.util.*;


public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        if(str1.equals(str2))return str1;
//         循环从1中取字符组成字符串，判断2中是否包含该子串，若包含则继续取，直到取到不包含的字符为止，与最大子串判断长度进行替换
        String maxStr="";
        for(int i=0;i<str1.length();i++){
            String s = "";
//             剩余长度比最大子串长度还小，不用再比
            if(maxStr.length()>str1.length()-i)break;
            for(int j=i;j<str1.length();j++){
                s += str1.charAt(j);
                if(str2.contains(s)){
                    if(maxStr.length()<s.length()) maxStr=s;
                }
                if(!str2.contains(s)){
                    break;
                }
            }
        }
        
        return maxStr;
    }
}

增加contains方法的代码

import java.util.*;


public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        if(str1.equals(str2))return str1;
//         循环从1中取字符组成字符串，判断2中是否包含该子串，若包含则继续取，直到取到不包含的字符为止，与最大子串判断长度进行替换
        String maxStr="";
        for(int i=0;i<str1.length();i++){
            StringBuilder s = new StringBuilder("");
//             剩余长度比最大子串长度还小，不用再比
            if(maxStr.length()>str1.length()-i)break;
            for(int j=i;j<str1.length();j++){
                s.append(str1.charAt(j));
                boolean contain =  contain(s.toString(),str2);
                if(contain){
                    if(maxStr.length()<s.length()) maxStr=s.toString();
                }else{
                    break;
                }
//                 if(str2.contains(s.toString())){
//                     if(maxStr.length()<s.length()) maxStr=s.toString();
//                 }
//                 if(!str2.contains(s)){
//                     break;
//                 }
            }
        }
        
        return maxStr;
    }
    
    public boolean contain(String s,String str){
        boolean contain = false;
        if(s.length()>str.length())return contain;
        for(int i=0;i<str.length();i++){
            if(str.length()-i<s.length())break;
            int j=0,x=i;
            while(j<s.length() && x<str.length()){
                if(str.charAt(x)==s.charAt(j)){
                    x++;j++;
                    if(j==s.length())contain=true;
                }else{
                    break;
                }
            }
        }
        return contain;
    }
}