8.30阿里笔试算法题第二题
是笔试完做的，没有验证。
注意题目有个bug，应该是子串而不是子序列，子序列的话答案应该不止14个
其实就是暴力法在第一个序列里面找到符合长度的子串，然后在第二个序列里面找到符合长度的子串，然后一一匹配，数能够有多少个匹配的，算编辑距离的时候要用到动态规划。
第一题实在不会做，哪位大神做出来了吗。
int fun(vector<string> s1, vector<string> s2) {
vector<vector<int> > dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
for (int i = 1; i <= s1.size(); ++i)
dp[i][0] = i;
for (int i = 1; i <= s2.size(); ++i)
dp[0][i] = i;
for (int i = 1; i <= s1.size(); ++i) {
for (int j = 1; j <= s2.size(); ++j) {
int replace_step = 0;
if (s1[i - 1] == s2[j - 1])
replace_step = dp[i - 1][j - 1];
else
replace_step = dp[i - 1][j - 1] + 1;
replace_step = min(replace_step, dp[i - 1][j] + 1);
dp[i][j] = min(replace_step, dp[i][j - 1] + 1);
}
}
return dp[s1.size()][s2.size()];
}
std::string findSimilarPairs(int threshold, int minSeqLen, int maxSeqLen, std::vector<std::string>& list1, std::vector<std::string>& list2) {
vector<vector<string>> res1, res2;
for (int i = 0; i < list1.size(); i++) {
for (int j = minSeqLen; j <= maxSeqLen; j++) {
if (i + j - 1 < list1.size()) {
vector<string> tmp;
for (int k = i; k <= i+j-1;k++) {
tmp.push_back(list1[k]);
}
res1.push_back(tmp);
}
}
}
for (int i = 0; i < list2.size(); i++) {
for (int j = minSeqLen; j <= maxSeqLen; j++) {
if (i + j - 1 < list2.size()) {
vector<string> tmp;
for (int k = i; k <= i + j - 1; k++) {
tmp.push_back(list2[k]);
}
res2.push_back(tmp);
}
}
}
int count = 0;
vector<pair<vector<string>, vector<string>>> aa;
for (auto i : res1) {
for (auto j : res2) {
if (fun(i, j) <= threshold) {
aa.push_back(make_pair(i, j));
count++;
}
}
}
cout << count;
return 0;
}