Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/249.html
We can shift a string by shifting each of its letters to its successive letter.
- For example,
"abc"
can be shifted to be"bcd"
.
We can keep shifting the string to form a sequence.
- For example, we can keep shifting
"abc"
to form the sequence:"abc" -> "bcd" -> ... -> "xyz"
.
Given an array of strings strings
, group all strings[i]
that belong to the same shifting sequence. You may return the answer in any order.
Example 1:
Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"] Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]
Example 2:
Input: strings = ["a"] Output: [["a"]]
Constraints:
1 <= strings.length <= 200
1 <= strings[i].length <= 50
strings[i]
consists of lowercase English letters.
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 = defaultdict(list) >>> b = defaultdict([]) Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: first argument must be callable or None >>> ord('c') 99 >>> ord('c') - ord('a') 2 >>> ord('d') - 2 98 >>> chr(98) 'b' >>> 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] ''' from collections import defaultdict 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 }