Longest Common Substring

Medium Longest Common Substring

32%

Accepted

Given two strings, find the longest common substring.

Return the length of it.

Have you met this question in a real interview? 

Yes

Example

Given A = "ABCD", B = "CBCE", return 2.

Note

The characters in substring should occur continuously in original string. This is different with subsequence.

Challenge

O(n x m) time and memory.

public class Solution {
    /**
     * @param A, B: Two string.
     * @return: the length of the longest common substring.
     */
    public int longestCommonSubstring(String A, String B) {
        // write your code here
        int maxLen = 0;
        int m = A.length(), n = B.length();
        int[][] record = new int[m+1][n+1];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(A.charAt(i) == B.charAt(j)){
                    record[i+1][j+1] = record[i][j]+1;
                }
                maxLen = Math.max(maxLen, record[i+1][j+1]);
            }
        }
        return maxLen;
    }
}