题目
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.
答案
The key here is to recognize that strings in the same group can be transformed to a unique representation.
class Solution {
public List<List<String>> groupStrings(String[] strings) {
// Map: number of gaps -> index in the list
Map<String, Integer> map = new HashMap<>();
List<List<String>> list = new ArrayList<>();
for(String s : strings) {
int c = s.charAt(0) - 'a';
int offset = 26 - c;
StringBuilder sb = new StringBuilder();
for(int i = 0; i < s.length(); i++) {
int c2 = s.charAt(i) - 'a';
int t = (c2 + offset) % 26;
sb.append((char)((int)'a' + t));
}
String curr = sb.toString();
if(!map.containsKey(curr)) {
list.add(new ArrayList<String>());
List<String> strlist = list.get(list.size() - 1);
strlist.add(s);
map.put(curr, list.size() - 1);
}
else {
int list_ind = map.get(curr);
List<String> strlist = list.get(list_ind);
strlist.add(s);
}
}
return list;
}
}
