算法篇：最长公共子串（牛客）

题目描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

解题思路

1. 定义两层循环，分别将两个字符串逐个比较，如果有相等的，就让info数组值+1，然后得出最长的子串长度，和重复字串出现的位置，最后进行字符串切割

代码1

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 == null || str2 == null){
            return null;
        }
        String myStr = null;
        int m = str1.length();//str1的长度
        int n = str2.length();//str2的长度
        int maxLen = 0;//最长重复子串的长度
        int maxIndex = 0;//最长重复子串最后一个元素出现的位置
        int info[][] = new int[m][n];//用来记录str1[0~i-1]和str2[0~j-1] 的最长公共子串的长度
        for(int i=0; i<m; i++){//str1循环
            for(int j=0; j<n; j++){//str2循环
                if(str1.charAt(i) == str2.charAt(j)){//如果有相等的
                    if(i == 0 || j == 0){
                        info[i][j] = 1;//如果是第一个相等的，就是一，加这个判断是因为，i-1和j-1必须要大于0
                    }else{
                        info[i][j] = info[i-1][j-1]+1;//等于前一个info+1
                    }
                }
                if(maxLen < info[i][j]){//如果最长的子串长度小于info，那就证明开始拿到的不是最长的子串，所以重新赋值
                    maxLen = info[i][j];//最长字串的长度
                    maxIndex = i;//最长子串出现的地方
                }
            }
        }
        if(maxLen == 0){//如果长度为0 ，那就证明没有重复的，就返回null
            return null;
        }
        myStr = str1.substring(maxIndex - maxLen + 1,maxIndex + 1);//进行切割
        return myStr;
    }
}
           

代码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 start = 0;
        int end = 0;
        String result = "";
        while(end <= str2.length()){
            String temp = str2.substring(start,end);
            if(str1.contains(temp)){
                result = temp;
            }else{
                start++;
            }
            end++;
        }
        return result;
    }
}