两种思路Java

最长公共子串

http://www.nowcoder.com/questionTerminal/f33f5adc55f444baa0e0ca87ad8a6aac

两种实现方式可以优化哦！

第一种字符串包含，内存占用较大

maxlen :记录最长字串的长度 index：最长字串的下标

思路: str1 包含str2 中的最长字串

        int maxLength = 0;
        int index = 0;
        for(int i = 0; i < str2.length(); i++){
            for(int j = i+1; j <= str2.length(); j++){
                if(str1.contains(str2.substring(i, j)) ){
                    if(maxLength < j-i){
                        maxLength = j-i;
                        index = i;
                    }
                } else break;
            }
        }
        if( maxLength == 0 ){ //没有相同的字符串
            return "-1";
        }
        return str2.substring(index,index + maxLength);

第二种：动态规划

思路：二维数组，下图：str1: sabgc ,s2:abcg, 二维数组，相同的标记为1 ，不同的标0，可以看出斜对角为1 的就是最长的字串。第一个一样标记1，第二个对角相同，值应该是x,y下标-1 的值在+1，记录的就是长度。

        if (str1 == null || str2 == null || str1.equals(" ") || str2.equals(" ")) {
            return "-1";
        }
        //动态规划  二维数组，斜下来就是最长字串
        int str1len = str1.length();
        int str2len = str2.length();
        int maxLen = 0;
        int index = 0;
//        定义一个二维数组
        int[][] dp = new int[str1len][str2len];
        //第一步：划分
        for (int i = 0; i < str1len; i++) {
            for (int j = 0; j < str2len; j++) {
                if (str1.charAt(i) == str2.charAt(j)) {
                    if (j == 0 && i == 0){
                        dp[i][j]=1;
                        maxLen = dp[i][j];
                        index = i;
                    } else{
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                        if(maxLen <= dp[i][j]){
                            maxLen = dp[i][j];
                            index = i;
                        }
                    }
                }
            }
        }
        if( maxLen==0 ){
            return "-1";
        }
        return str1.substring(index-maxLen+1,index+1);