The basic idea is to shift all words back into the form starting with 'a'. (all digits must shift the same distance). If the two words share the same shifted word, it means they actually come from the same shift group.
Step 1: get the distance each word must shift (leftward, it actually does not matter). Use the first character of a Word, and compute the distance.
int dist = str.charAt(0) - 'a';
Step 2: shift all characters through the same distance.
使用hashmap，关键字key为首个字符串相邻元素的差值和，如果差值为负数，则加上26，比如“abc”的key是（‘a’-‘b’+26）+（‘b’-‘c’+26），再转化成字符串。
Shawngbk
commented
7 years ago
The basic idea is to shift all words back into the form starting with 'a'. (all digits must shift the same distance). If the two words share the same shifted word, it means they actually come from the same shift group. Step 1: get the distance each word must shift (leftward, it actually does not matter). Use the first character of a Word, and compute the distance. int dist = str.charAt(0) - 'a';
Step 2: shift all characters through the same distance. 使用hashmap，关键字key为首个字符串相邻元素的差值和，如果差值为负数，则加上26，比如“abc”的key是（‘a’-‘b’+26）+（‘b’-‘c’+26），再转化成字符串。
这样，shifted字符串的关键字key相同。
这个题目一看就是HashMap，刚开始我说那String的长度来存作为key，但是发现相同长度的string可能不为同一阵营 所以后面该用一个新的string，就是把每两个字符之间的差存起来，写出一个string ["eqdf", "qcpr"]。 ((‘q’ - ‘e‘) + 26) % 26 = 12, ((‘d’ - ‘q‘) + 26) % 26 = 13, ((‘f’ - ‘d‘) + 26) % 26 = 2 ((‘c’ - ‘q‘) + 26) % 26 = 12, ((‘p’ - ‘c‘) + 26) % 26 = 13, ((‘r’ - ‘p‘) + 26) % 26 = 2 *所以"eqdf"和"qcpr"是一组shifted strings。
以字符串第一个字符为基准，将字符串标准化为小写字母a开头的字符串。
public class Solution { public List<List> groupStrings(String[] strings) {
Arrays.sort(strings);
Map<String, List> map = new HashMap<>();
for(int i = 0; i < strings.length; i++) {
char[] element = strings[i].toCharArray();
if(element.length != 0) {
int distance = element[0] - 'a';
for(int j = 0; j < element.length; j++) {
element[j] = (char)((element[j] - 'a' - distance + 26) % 26 + 'a');
}
}
String key = new String(element);
List list = map.get(key);
if(list == null) {
list = new ArrayList();
map.put(key, list);
}
list.add(strings[i]);
}
List<List> res = new ArrayList<List>();
res.addAll(map.values());
return res;
}
}