-
Notifications
You must be signed in to change notification settings - Fork 2
/
GroupShiftedStrings.java
70 lines (60 loc) · 1.96 KB
/
GroupShiftedStrings.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package Leetcode;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* @author kalpak
* 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"]
* ]
*/
public class GroupShiftedStrings {
public static List<List<String>> groupStrings(String[] strings) {
Map<String, List<String>> stringGroups = new HashMap<>();
List<List<String>> result = new ArrayList<>();
for(String str : strings) {
String key = hashString(str);
List<String> temp = stringGroups.getOrDefault(key, new ArrayList<>());
temp.add(str);
stringGroups.put(key, temp);
}
for(String key : stringGroups.keySet()){
result.add(stringGroups.get(key));
}
return result;
}
private static String hashString(String word) {
char[] temp = word.toCharArray();
StringBuilder hashKey = new StringBuilder();
for(int i = 1; i < temp.length; i++) {
int diff = temp[i] - temp[i - 1];
// Consider az and ba
// where az = 0->25 and ba = 0->-1
if(diff < 0){
diff += 26;
}
hashKey.append(diff);
hashKey.append(",");
}
return hashKey.toString();
}
public static void main(String[] args) {
String[] wordSet = new String[]{"abc","bcd","acef","xyz","az","ba","a","z"};
List<List<String>> result = groupStrings(wordSet);
System.out.println(result);
}
}