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

題目描述

給定兩個字元串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;
    }
}