4ms Easy C++ Solution with Explanations


  • 29

    The key to this problem is how to identify strings that are in the same shifting sequence. There are different ways to encode this.

    In the following code, this manner is adopted: for a string s of length n, we encode its shifting feature as "s[1] - s[0], s[2] - s[1], ..., s[n - 1] - s[n - 2],".

    Then we build an unordered_map, using the above shifting feature string as key and strings that share the shifting feature as value. We store all the strings that share the same shifting feature in a vector. Well, remember to sort the vector since the problem requires them to be in lexicographic order :-)

    A final note, since the problem statement has given that "az" and "ba" belong to the same shifting sequence. So if s[i] - s[i - 1] is negative, we need to add 26 to it to make it positive and give the correct result. BTW, taking the suggestion of @StefanPochmann, we change the difference from numbers to lower-case alphabets using 'a' + diff.

    The code is as follows.

    class Solution {
    public:
        vector<vector<string>> groupStrings(vector<string>& strings) {
            unordered_map<string, vector<string> > mp;
            for (string  s : strings)
                mp[shift(s)].push_back(s);
            vector<vector<string> > groups;
            for (auto m : mp) {
                vector<string> group = m.second;
                sort(group.begin(), group.end());
                groups.push_back(group);
            }
            return groups;
        }
    private:
        string shift(string& s) {
            string t;
            int n = s.length();
            for (int i = 1; i < n; i++) {
                int diff = s[i] - s[i - 1];
                if (diff < 0) diff += 26;
                t += 'a' + diff + ',';
            }
            return t;
        }
    };

  • 0

    Nice solution. And I see you're embracing range-based loops now :-)

    Just one idea that's shorter and I guess slightly faster: t += 'a' + diff;. But your way is of course fine as well.


  • 1

    Hi, Stefan. I try your suggestion and the code just takes 4 ms, actually much faster than using to_string :-)

    But I guess it would be much safer to add an additional ,. For example, if not using the , for separation, both "az" and "ach" will have the same shifting feature "25". So I use t += 'a' + diff + ','.


  • 1

    if not using the "," for separation, both "az" and "ach" will have the same shifting feature "25"

    No, "az" becomes "z" and "ach" becomes "cf". Not "25".


  • 0

    Oh, yeah. I see now. Since it is added by a and becomes a character, the problem is automatically fixed :-)


  • 0

    I'm not sure that adding 'a' is necessary. It does get accepted without. But I'm a little afraid at least of the null character, as that at least in C denotes the end of a string and I don't know how C++ handles it. So I added 'a' to be on the safe side and because it's just nicer in case anyone ever looks at the strings (like for debugging).


  • 0

    Hi, Stefan. I guess C++ will handle it as we desire. I test the code without adding 'a' using the test case strings = ["a", "aa", "ac", "acc"] and C++ just groups each of them into a single group, as it should.


  • 0

    Thanks. Good test case. Though you didn't necessarily test C++ but only the C++ implementation that you or LeetCode use. I tried finding it documented but failed. Closest thing I found is the claim "allowing the NUL byte to be in the string", but there's no reference.


  • 0

    Hi, Stefan. Thank you for your efforts :-)


  • 1
    C

    Hi, thanks for your great solution. Here is the java version solution based on your idea.
    Thanks for your discussion with Stefan too. I learned a lot.

    public class Solution {
        public List<List<String>> groupStrings(String[] strings) {
            Map<String, List<String>> map = new HashMap<>();
            for(int i=0; i<strings.length; i++) {
                String key = shiftPattern(strings[i]);
                if(map.containsKey(key)) {
                    map.get(key).add(strings[i]);
                }else {
                    map.put(key, new ArrayList<String>());
                    map.get(key).add(strings[i]);
                }
            }
            List<List<String>> result = new ArrayList<>();
            for(String key : map.keySet()) {
                List<String> g = map.get(key);
                Collections.sort(g);
                result.add(g);
            }
            return result;
            
        }
        public String shiftPattern(String s) {
            String key = "";
            for(int i=1; i<s.length(); i++) {
                int diff = (int)(s.charAt(i)-s.charAt(i-1));
                if(diff < 0) { diff += 26; }
                key += 'a' + diff; //alternatively, key += 'a' + diff + ',';
            }
            return key;
        }
    }

  • 1

    Hi, connie0817. Thanks for your clear Java code. Well, I am very new to Java, but the following part

    if(map.containsKey(key)) {
        map.get(key).add(strings[i]);
    }else {
        map.put(key, new ArrayList<String>());
        map.get(key).add(strings[i]);
    }
    

    may be simplified to

    if (!map.containsKey(key))
        map.put(key, new ArrayList<String>());
    map.get(key).add(strings[i]);

  • 0
    C

    oh yes! You are right! Thank you very much!


  • 0
    G

    is "if (diff < 0) diff += 26;" necessary?


  • 0

    @GO You can simply verify whether it is necessary by removing it and checking the results...


  • 0
    G

    well,i'm not subscribe,so cannot use the oj,but i will verify on my local machine,thanks anyway.


  • 0

    @GO That line is necessary, try this case: ["az","yx"].

    BTW, I am sorry that I forgot this problem is not free to everyone...


  • 0
    G

    Thanks,now i understand.


  • 0
    H

    it is not necessary to encode the sequence into a human readable string though, just take the ascii difference, stack them into a string whatever it looks like as a key.


  • 0
    L

    I think you should write t+= 'a' + diff; t += ',' instead a single line code: t += 'a' + diff + ',';
    Because the operator+ for string will only accept one char each time.


  • 0
    Y

    Great solution! A small place, is it possible modify

       int diff = s[i] - s[i - 1];
        if (diff < 0) diff += 26;
    

    to

     int diff = (s[i] + s[i - 1] + 26) % 26;  
    

    Which is better?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.