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.
For example, given:["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
A solution is:
[
["abc","bcd","xyz"],
["az","ba"],
["acef"],
["a","z"]
]
把字符串按相同规则分组。 一看就懵圈， 不会呀， 么么哒。 ╰(￣ω￣ｏ)
借助一个offset 把字符都降为最字符串， 如xyz，bcd 降级后为皆为abc， 显然他们三个应该在一组。 放到hashmap里存好。
public List> groupStrings(String[] strings) {
HashMap> map = new HashMap<>();
for(String str : strings){
int offset = str.charAt(0) - 'a';
String key = "";
for(int i = 0; i < str.length(); i++){
char ch = (char)(str.charAt(i) - offset);
if(ch < 'a'){
ch += 26;
}
key += ch;
}
if(!map.containsKey(key)){
map.put(key, new ArrayList());
}
map.get(key).add(str);
}
List> ret = new ArrayList>();
Setkeyset = map.keySet();
for(String key: keyset){
ret.add( map.get(key));
}
return ret;
}
