<h3>Given two strings ‘X’ and ‘Y’, find the length of the longest common substring.</h3>
For example, if the given strings are “GeeksforGeeks” and “GeeksQuiz”, the output should be 5 as longest common substring is “Geeks”
这道题目不是Leetcode 上的。一开始觉得很难，看了答案后发现dp做简单。
dp就是这样，想不到，觉得这道题目太变态了，想到了，觉得好简单。
但是，往往想到，都是建立在，看了答案基础上的。
平常心。
My code:
public int longestCommonString(String s1, String s2) {
if (s1 == null || s1.length() == 0)
return 0;
if (s2 == null || s2.length() == 0)
return 0;
int[][] dp = new int[s1.length()][s2.length()];
int max = Integer.MIN_VALUE;
for (int i = 0; i < s1.length(); i++) {
if (s2.charAt(0) == s1.charAt(i)) {
dp[i][0] = 1;
max = 1;
}
}
for (int i = 0; i < s2.length(); i++) {
if (s1.charAt(0) == s2.charAt(i)) {
dp[0][i] = 1;
max = 1;
}
}
for (int i = 1; i < s1.length(); i++) {
for (int j = 1; j < s2.length(); j++) {
if (s1.charAt(i) == s2.charAt(j))
dp[i][j] = dp[i - 1][j - 1] + 1;
max = Math.max(max, dp[i][j]);
}
}
return max;
}
就是建立一个dp[][] 数组用来记录 i, j 结尾的最长尾字符串长度。
然后一步步递推。
参考网页：
http://www.geeksforgeeks.org/longest-common-substring/
Anyway, Good luck, Richardo！
