Description
??Given two strings, find the longest common substring. Return the length of it.
Note: The characters in substring should occur continuously in original string. This is different with subsequence.
Example1:
Example 1:
Input: "ABCD" and "CBCE"
Output: 2
Explanation:
Longest common substring is "BC"
Example 2:
Input: "ABCD" and "EACB"
Output: 1
Explanation:
Longest common substring is 'A' or 'C' or 'B'
Challenge: O(n x m) time and memory.
思路：
??這是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃題，定義dp矩陣勿决，dp[i][j]表示A串匹配到i乒躺，B串匹配到j(luò)時(shí)的最大公共長(zhǎng)度。dp有A.length()+1行低缩，有B.length()列嘉冒。第一行與第一列都為0；有狀態(tài)轉(zhuǎn)移方程
??????dp[i][j]=dp[i-1][j-1]+1 ,A[i]==B[j]
??????dp[i][j]=0 ,A[i]!=B[j]
最后返回dp的最大值即為最長(zhǎng)公共子串長(zhǎng)度咆繁，代碼如下：
class Solution {
public:
/**
* @param A: A string
* @param B: A string
* @return: the length of the longest common substring.
*/
int longestCommonSubstring(string &A, string &B) {
// write your code here
int res = 0, m = A.size(), n = B.size();
if (m == 0 || n==0) return 0;
//int dp[m+1][n+1];
std::vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for (int i=1; i<=m; ++i) {
for (int j=1; j<=n; ++j) {
if (A[i-1] == B[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
}
else {
dp[i][j] = 0;
}
res = max(res, dp[i][j]);
}
}
return res;
}
};
類(lèi)似題目：
