通配*|滚动hash

lc2489

lc1983

差值前缀和+枚举右维护左

class Solution {
public:
int widestPairOfIndices(vector<int>& nums1, vector<int>& nums2)
{
int n=nums2.size();
vector<int> d(n+1);
unordered_map<int,int> hash;
hash[0]=0;//init
int ret=0;
for(int i=1;i<=n;i++)
{
d[i]=d[i-1]+nums1[i-1]-nums2[i-1];
if(hash.count(d[i]))
ret=max(ret,i-hash[d[i]]);
else
hash[d[i]]=i;
}
return ret;
}
};

lc3606

先按下标排序，在转换为字符串

class Solution {
public:
vector<string> validateCoupons(vector<string>& code, vector<string>& businessLine, vector<bool>& isActive)
{
int n=code.size();
vector<int> ret;
set<string> set={"electronics","grocery","pharmacy","restaurant"};
unordered_map<string,int> hash;
unordered_map<int,string> hash2;

for(int i=0;i<n;i++)
{
if(isActive[i]==true)
{
if(set.count(businessLine[i]))
{
bool check=true;
string tmp=code[i];
for(int j=0;j<code[i].size();j++)
{
if(isalnum(tmp[j]) || tmp[j]=='_')
check=true;
else
{
check=false;
break;
}
}
if(check && !tmp.empty())
{
ret.push_back(i);
}
}
}
}


sort(ret.begin(),ret.end(),[&](int& a,int& b)
{
string b1=businessLine[a],b2=businessLine[b];
if(b1!=b2)
{
return b1<b2;
}
return code[a]<code[b];
});
//先按下标排序，在转换为字符串
vector<string> ans;
for(auto& r:ret)
ans.push_back(code[r]);

return ans;

}
};

lc1554

滚动hash优化

unordered_map<int, vector<int>> hs;

hash给每个字符串“遮掉一位”做标记

遇到重复标记时，真实验证这俩串是不是只遮掉的那一位不同，是就返回true

class Solution {
public:
bool differByOne(vector<string>& dict) {
// self-defined hash, mod 5801, any big prime fine
// strict, check if there is hash clashing

int mod(5801), m(dict[0].length()), mod_pows[m];
mod_pows[0] = 1;
for (int i = 1; i < m; ++i)
mod_pows[i] = mod_pows[i - 1] * 27 % mod;

unordered_map<int, vector<int>> hs; // we can also use deque<int> here

for (int k = 0; k < dict.size(); ++k) {
int h = 0;
for (char& c: dict[k])
h = (27 * h + c - 'a' + 1) % mod;
for (int i = 0; i < m; ++i) {
int t = (h - mod_pows[m - i - 1] * (dict[k][i] - 'a' + 1) % mod + mod) % mod;
if (hs.count(t)) {
for (const int& x: hs[t]) {
int kk(x / m), ii(x % m);
if (ii == i) {
bool checked = true;
for (int p = 0; p < m; ++p) {
if (p == i) continue;
if (dict[k][p] != dict[kk][p]) {
checked = false;
break;
}
}
if (checked) return true;
}
}
}
hs[t].push_back(m * k + i);
}
}

return false;
}
};

mle 通配* hash

class Solution {

public:

bool differByOne(vector<string>& dict) {

if (dict.empty()) return false;

int len = dict[0].size();

unordered_set<string> seen;

for (auto& s : dict) {

// 通配* hash

for (int i = 0; i < len; ++i) {

string key = s;

key[i] = '*'; // 把第i位替换为通配符，代表忽略该位的差异

if (seen.count(key)) {

return true;

}

seen.insert(key);

}

}

return false;

}

};