Question

Formatted question description: https://leetcode.ca/all/249.html

 249	Group Shifted Strings

 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"],
 Return:

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


 Note: For the return value, each inner list's elements must follow the lexicographic order.

Algorithm

The relative distance between each letter of the string and the first character is equal.

For example, abc and efg are mutually offset. For abc, the distance between b and a is 1, and the distance between c and a is 2. For efg, the distance between f and e is 1, and the distance between g and e is 2.

Let’s look at another example. The distance between az and yx, z and a is 25, and the distance between x and y is also 25 (direct subtraction is -1, which is the reason for adding 26 and taking the remainder).

Then, in this case, all strings that are offset from each other have a unique distance difference. According to this, the mapping can be well grouped.

Code

import java.util.*;

public class Group_Shifted_Strings {
    class Solution {
        public List<List<String>> groupStrings(String[] strings) {

            List<List<String>> result = new ArrayList<>();

            if (strings == null || strings.length == 0) {
                return result;
            }

            Map<String, List<String>> map = new HashMap<>();

            for (String str : strings) {
                String key = findKey(str);
                if (map.containsKey(key)) {
                    map.get(key).add(str);
                } else {
                    List<String> list = new ArrayList<>();
                    list.add(str);
                    map.put(key, list);
                }
            }

            // iterate the map
            result.addAll(map.values());

            return result;
        }

        private String findKey(String str) {
            // @note: should check for empty string
            if (str.length() == 0) {
                return "";
            }

            StringBuilder sb = new StringBuilder();

            int distance = str.charAt(0) - 'a'; // @note: key is shifting word to start with 'a'

            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                char offset = (char) (c - distance);
                if (offset < 'a') {
                    offset = (char) (offset + 26);
                }
                sb.append(offset);
            }

            return sb.toString();
        }
    }
}

############

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        Map<String, List<String>> mp = new HashMap<>();
        for (String s : strings) {
            int diff = s.charAt(0) - 'a';
            char[] t = s.toCharArray();
            for (int i = 0; i < t.length; ++i) {
                char d = (char) (t[i] - diff);
                if (d < 'a') {
                    d += 26;
                }
                t[i] = d;
            }
            String key = new String(t);
            mp.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(mp.values());
    }
}

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<string>> mp;
        for (auto& s : strings) {
            int diff = s[0] - 'a';
            string t = s;
            for (int i = 0; i < t.size(); ++i) {
                char d = t[i] - diff;
                if (d < 'a') d += 26;
                t[i] = d;
            }
            cout << t << endl;
            mp[t].push_back(s);
        }
        vector<vector<string>> ans;
        for (auto& e : mp)
            ans.push_back(e.second);
        return ans;
    }
};

'''
>>> a = {"s":1, "t":2, "x":3}
>>> a
{'s': 1, 't': 2, 'x': 3}
>>> a.items()
dict_items([('s', 1), ('t', 2), ('x', 3)])
>>> a.values()
dict_values([1, 2, 3])
>>> list(a.values())
[1, 2, 3]
'''
class Solution:
    def groupStrings(self, strings: List[str]) -> List[List[str]]:
        mp = defaultdict(list)
        for s in strings:
            t = []
            diff = ord(s[0]) - ord('a')
            for c in s:
                d = ord(c) - diff
                if d < ord('a'):
                    d += 26
                t.append(chr(d))
            k = ''.join(t)
            mp[k].append(s)
        return list(mp.values())

############

class Solution(object):
  def groupStrings(self, strings):
    """
    :type strings: List[str]
    :rtype: List[List[str]]
    """
    d = {}
    ans = []
    single = []
    for s in strings:
      if len(s) == 1:
        single.append(s)
        continue
      hashcodeArray = []
      pre = ord(s[0]) - ord("a")
      for i in range(1, len(s)):
        hashcodeArray.append(str(((ord(s[i]) - ord("a")) - pre) % 26))
        pre = ord(s[i]) - ord("a")
      hashcode = ",".join(hashcodeArray)
      if hashcode not in d:
        d[hashcode] = [s]
      else:
        d[hashcode].append(s)
    for k in d:
      ans.append(d[k])
    if single:
      ans.append(single)
    return ans

func groupStrings(strings []string) [][]string {
	mp := make(map[string][]string)
	for _, s := range strings {
		k := ""
		for i := range s {
			k += string((s[i]-s[0]+26)%26 + 'a')
		}
		mp[k] = append(mp[k], s)
	}
	var ans [][]string
	for _, v := range mp {
		ans = append(ans, v)
	}
	return ans
}

249 - Group Shifted Strings

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions