最长公共子串

题目描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串，如果最长公共子串为空，输出-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 "-1";
        int len1 = str1.length();
        int len2 = str2.length();
        if (len1 == 0 || len2 == 0) 
            return "-1";
        int[][] dp = new int[len1+1][len2+1];
        int index = 0;
        int max_len = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i-1) == str2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if (dp[i][j] > max_len) {
                        max_len = dp[i][j];
                        index = i;
                    }
                }
            }
        }
        return max_len == 0? "-1": str1.substring(index-max_len, index);
    }
}