Given a list of strings dict where all the strings are of the same length.
Return true if there are 2 strings that only differ by 1 character in the same index, otherwise return false.
Solution
对于每个字符串，我们用哈希将其映射为数。然后对于每个位置（即删除的位置），我们枚举每个字符串，得到该字符串删去该位置之后的哈希值。这里我们用一个 /(map/) 来存储此时哈希值对应的字符串下标。所以我们就可以在 /(map/) 里面查找其对应的下标，如果相同的话，那么就是 /(true/)
点击查看代码
class Solution {
private:
int mod = 1e9+7;
vector<long long> hash;
int p = 37;
public:
bool differByOne(vector<string>& dict) {
int n=dict.size();
int m = dict[0].size();
hash = vector<long long> (n,0);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
hash[i]=(long long)(p*hash[i]+(dict[i][j]-'a'))%mod;
}
}
for(long long j=m-1, bs = 1;j>=0;j--){
// hash_val -> pos
unordered_map<long long,vector<long long>> mp;
for(long long i=0;i<n;i++){
long long res = (mod+hash[i]-bs*(dict[i][j]-'a')%mod)%mod;
if(mp.find(res)!=mp.end()){
auto f = mp.find(res);
for(auto ele:f->second){
if(equal(begin(dict[i]),begin(dict[i])+j, begin(dict[ele])) && equal(begin(dict[i])+j+1, end(dict[i]), begin(dict[ele])+j+1))
return true;
}
}
mp[res].push_back(i);
}
bs=bs*p%mod;
}
return false;
}
};
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/288081.html