[Google] LeetCode 1554 Strings Differ by One Character 哈希
2022/9/7 6:22:48
本文主要是介绍[Google] LeetCode 1554 Strings Differ by One Character 哈希,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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; } };
这篇关于[Google] LeetCode 1554 Strings Differ by One Character 哈希的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-01got an unexpected keyword argument
- 2024-03-30维多利亚的秘密 golang入坑系统
- 2024-03-29mongodb sort by date
- 2024-03-29go swagger
- 2024-03-25mongodb cdc
- 2024-03-25how to use go in vscode
- 2024-03-22mongooseserverselectionerror: connect econnrefused ::1:27017
- 2024-03-21pymongo insert_many
- 2024-03-18projection mongodb
- 2024-03-14clickhouse-go