题解 | #最长公共子串#
最长公共子串
https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac
class Solution {
public:
string LCS(string str1, string str2) {
vector<vector<unsigned short>> dp;
unsigned short record = 0;
int end_pos;
for (int i = 0; i <= str1.size(); ++i)
dp.push_back(vector<unsigned short>(str2.size() + 1));
for (int i = 1; i <= str1.size(); ++i) {
for (int j = 1; j <= str2.size(); ++j) {
if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > record) {
record = dp[i][j];
end_pos = i;
}
}
}
}
return str1.substr(end_pos - record, record);
}
};
DP数组定义为：以str[i-1] str[j-1]为结尾的字串的长度
同时需要记录一个全局最长答案，以及此答案对应的字母串的字母下标。我们最后是需要通过这个信息去返回字符串本身的。
PS：
1. 这里因为字符串长度5000以内，因此用unsigned short降低内存占用
2. substr方法注意是（pos，count），而不是（pos，end）。这里跟Python完全不同。
