讨论/《哈希表》 - 移位字符串分组/
《哈希表》 - 移位字符串分组
共 1 个回复

cpp
4ms
7.6MB

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        vector<vector<string>>ans;
        unordered_map<string,int> hmap;
        int layer=0;
        while(!strings.empty()){ //循环开始
            string tmp=strings.back(); //tmp用于下述位移操作
            string aa=tmp; //aa用于保存原始字符串
            strings.pop_back();
            
            if(tmp[0]!='a'){ //将全部字符串移位到以'a'开头
                int offset=int(tmp[0]-'a'); //计算移位距离
                for(int t=0;t<tmp.size();t++){
                    tmp[t]=tmp[t]-offset;
                    if(tmp[t]<'a')tmp[t]+=26;//对类似"ba"的字符串进行移位后修复
                }
            }//位移结束
            
            
            if(!hmap.count(tmp)){ //开始存入答案
                //当该字符串分组未出现过时 ans增加一层
                //并将当前分组规则所在ans的层数写入哈希映射
                vector<string>newlayer;
                ans.push_back(newlayer);
                ans[layer].push_back(aa);
                hmap[tmp]=layer++;
            }
            else{
                //当之前已存在该分组时 根据哈希映射的值写入ans对应层数
                ans[hmap[tmp]].push_back(aa);
            }//存入答案结束
        }//循环结束
        return ans;
    }
};