class Solution { public: /** * longest common substring * @param str1 string字符串 the string * @param str2 string字符串 the string * @return string字符串 */ int dpMatrix[5001][5001] = {0}; int maxIdx; int maxJdx; int maxLen = 0; /* i和j代表以str1[i]结尾和str2[j]结尾的子串 状态转移方程为: 1) i = 0 or j = 0, dpMatrix = 0 2) str1[i] == str2[j] dpMatrix[i][j] = dpMatrix[i-1][j-1] + 1 3) str1[i] != str2[j] dpMatrix[i][j] = 0 使用maxLen记录最大长度,maxIdx和maxJdx记录最长子串结尾在str1和str2的index, LCS就是str1[maxIdx-maxLen] */ string LCS(string str1, string str2) { // write code here for(int i = 1; i < str1.size()+1; i++) { for(int j = 1; j < str2.size()+1; j++) { if(str1[i - 1] != str2[j - 1]) { dpMatrix[i][j] = 0; } else { dpMatrix[i][j] = dpMatrix[i - 1][j - 1] + 1; if (dpMatrix[i][j] > maxLen) { maxLen = dpMatrix[i][j]; maxIdx = i; maxJdx = j; } } } } return str1.substr(maxIdx - maxLen, maxLen); } };