京东 相似字符串 不知道是否正确
有没有大佬能不能帮忙看一下相似字符串这个对不对,当时没做出来,今天才写了一下,求各位不吝赐教!
//找到S的所有与T长度相同的子串
set<string> Substr(string S, string T) {
set<string> res;
int lens = S.length(), lent = T.length();
for (int i = 0; i <= lens - lent; ++i)
res.insert(S.substr(i, lent));
return res;
}
int solve(string S, string T) {
int lens = S.length(), lent = T.length(), result = 0;
if (lens == 0 || lent == 0) return 0;
else if (lent == 1) {
set<char> res;
for (int i = 0; i < lens; ++i)
res.insert(S[i]);
return res.size();
}
set<string> Substrs = Substr(S, T);
int arr[26];
for (set<string>::iterator it = Substrs.begin(); it != Substrs.end(); it++) {
string str = *it;
memset(arr, -1, sizeof(arr));
bool flag = 1;
for (int i = 0; i < lent; ++i) {
int loc = T[i] - 'a'; //key point
if (arr[loc] == -1) arr[loc] = T[i] - str[i];
else {
char c = str[i] + arr[loc];
if (c != T[i]) {
flag = 0;
break;
}
}
}
result += flag;
}
return result;
} 
查看8道真题和解析