京东 相似字符串 不知道是否正确
有没有大佬能不能帮忙看一下相似字符串这个对不对,当时没做出来,今天才写了一下,求各位不吝赐教!
//找到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; }