Problem: 249. 移位字符串分组
思路
- 类似于凯撒密码的归类方式,我们将所有能通过轮转得到的字符串放在一起,不难想到可以通过暴力来对每一个字符串匹配
- 对于字符串仔细观察可以发现每一个可以归类到一起的字符串的本质是相同的,不只是字符串长度,还有与左右字母之间的差值
- 综上,对于每一类字符串我们只需要将其转化为模板的样子就能判断是否能归类
- 我们的问题就是如何将字符转成一个标准的模板
- 考虑字符之间的相对关系,
- 我们设首位为0,后面的每一位对应的是字符串该位与前一位的差
- 如果小于0则加26,来保证模式字符串相等
解题方法
- 对于每一个字符串,计算其相对字符的模板字符串
- 查询哈希表,如果有则插入到相对的答案组中
- 没有就新开一个答案组
- 重复上述操作
复杂度
- 时间复杂度:
只遍历一次 $O(mn)$,m为字符串长度
- 空间复杂度:
运用了哈希表 $O(n)$
Code
class Solution {
public:
vector<vector<string>> groupStrings(vector<string>& strings) {
vector<vector<string>>res;
unordered_map<string,int>hash;//模板字符串及其对应的在答案的行数
for (auto &iter:strings){
string tmp="0_";
char a=iter[0];
int now;
for (int i=1;i<iter.size();i++){
now=iter[i]-a;
if (now<0)//保证模板的一致性
now+=26;
tmp+=to_string(now)+"_";
a=iter[i];
}
if (hash.find(tmp)!=hash.end()){
res[hash[tmp]].emplace_back(iter);
}
else{
hash[tmp]=res.size();
res.emplace_back(vector<string>(1,iter));
}
}
return res;
}
};