leetcode解题: Group Shifted Strings (249)

发表于 | 分类于

Given a string, we can “shift” each of its letter to its successive letter, for example: “abc” -> “bcd”. We can keep “shifting” which forms the sequence:

“abc” -> “bcd” -> … -> “xyz”
Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: [“abc”, “bcd”, “acef”, “xyz”, “az”, “ba”, “a”, “z”],
A solution is:

[
[“abc”,”bcd”,”xyz”],
[“az”,”ba”],
[“acef”],
[“a”,”z”]
]

解法1：Hash Function, Hash Table

此题一看就是用hashtable的一道题，但难点在于什么是hashtable的key，换句话说，要构造出一个function，使得grouped string有相同的key。
思考一下可以得出，如果将每个字符转化为和第一个字符的距离，变可以得出一样的key。这里要注意的是，difference可以是正也可以是负，那么就需要加上25或者是26之后再对26取余来做。
C++
涉及到了几个C++的syntax：

  • access map value：iterator->second, iterator->first
  • insert to the end of a vector: vector.push_back()
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class Solution {
    public:
        vector<vector<string>> groupStrings(vector<string>& strings) {
            unordered_map<string, vector<string>> map;
            for (auto str: strings) {
                string s = "";
                for (auto i : str) {
                    s += std::to_string((i - str[0] + 26) % 26) + " ";
                }
                if (map.find(s) != map.end()) {
                    map[s].push_back(str);
                } else {
                    vector<string> v;
                    v.push_back(str);
                    map[s] = v;
                }
            }
            vector<vector<string>> res;
            for (auto i = map.begin(); i != map.end(); ++i) {
                res.push_back(i->second);
            }
            return res;
        }
    };

Java

1