[Google Question][LeetCode] Group Shifted Strings

Problem: 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 non-empty strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

Example:

Input: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
Output: 
[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]

Approach: We can use hashmap here where the Gap string of a string is the key and value is the list of strings with same "Gap string" itself. A Gap string is build by the gap between the consecutive characters. For example for "abc", the Gap string will be "11" (b - a = 1, c - b = 1), for "bcd", Gap string is again "11" so we can put them into the same group.

We can iterate through all the strings and build this hashmap. Once we are done with all the strings we can simply return all the values of the hashmap.

Implementation in C#:

    public IList<IList<string>> GroupStrings(string[] strings) 

    {

        Dictionary<string, List<string>> sameGapStrings = new Dictionary<string, List<string>>();

        foreach (string str in strings)

        {

            StringBuilder gapString = new StringBuilder();

            for (int i = 1; i < str.Length; ++i)

            {

                int gap = str[i] - str[i - 1];

                if (gap < 0)

                {

                    gap += 26; //cyclic az => ba

                }

                gapString.Append(gap);

            }

            string gapKey = gapString.ToString();

            if (!sameGapStrings.ContainsKey(gapKey))

            {

                sameGapStrings[gapKey] = new List<string>();

            }

            sameGapStrings[gapKey].Add(str);

        }

        return new List<IList<string>>(sameGapStrings.Select(kvp => kvp.Value));

    }

Complexity: O(n) where n is the sum of number of characters of all the strings.