249 Group Shifted Strings

249. Group Shifted Strings​
1. Question
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:
1
"abc" -> "bcd" -> ... -> "xyz"
Copied!
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:
1
[
2
  ["abc","bcd","xyz"],
3
  ["az","ba"],
4
  ["acef"],
5
  ["a","z"]
6
]
Copied!
2. Implementation
(1) HashMap
思路: 这里比较巧妙的做法是根据每个词的character和它之前的character的偏移量作为key. 注意由于a - z = -25, 为了让计算的结果统一为正数，我们需要对结果 + 26 再 模26
1
class Solution {
2
    public List<List<String>> groupStrings(String[] strings) {
3
        List<List<String>> res = new ArrayList<>();
4
​
5
        if (strings == null || strings.length == 0) {
6
            return res;
7
        }
8
​
9
        Map<String, List<String>> map = new HashMap<>();
10
​
11
        for (String str : strings) {
12
            StringBuilder key = new StringBuilder();
13
​
14
            for (int i = 1; i < str.length(); i++) {
15
                int offset = (str.charAt(i) - str.charAt(i - 1) + 26) % 26;
16
                key.append(offset);
17
            }
18
​
19
            String k = key.toString();
20
            if (!map.containsKey(k)) {
21
                map.put(k, new LinkedList<>());
22
            }
23
            map.get(k).add(str);
24
        }
25
        res = new ArrayList<>(map.values());
26
        return res;
27
    }
28
}
Copied!
3. Time & Space Complexity
HashMap: 时间复杂度O(nL), 空间复杂度O(n)

66 Plus One

281 Zigzag Iterator

Last modified 2yr ago

Copy link

Contents

249. Group Shifted Strings

1. Question

2. Implementation

3. Time & Space Complexity

249. Group Shifted Strings​

1. Question

2. Implementation

3. Time & Space Complexity

249. Group Shifted Strings