题解 | #最长公共子串#

空间复杂度O(1),时间复杂度O(n^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
        int maxIndex = 0, max = 0;
        for(int i = 0; i < str1.length(); ++i){
            for(int j = 0; j < str2.length(); ++j){
                int count = 0, iTmp = i;
                while(iTmp < str1.length() && j < str2.length() && str1.charAt(iTmp) == str2.charAt(j)){
                    ++iTmp;
                    ++j;
                    ++count;
                }
                if(count != 0){
                    --j;
                }
                if(count > max){
                    maxIndex = i;
                    max = count;
                }
            }
        }
//         StringBuffer sb = new StringBuffer();
//         for(int i = maxIndex; i <= maxIndex + max - 1; ++i){
//             sb.append(str1.charAt(i));
//         }
        return str1.substring(maxIndex, maxIndex + max);
    }
}