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"]
]
与Group Anagrams类似. 维护一个HashMap, key是每个string 的 base型.
Time Complexity: O(n * strings.length), n 是每个string的平均长度.
Space: O(hm.size()), HashMap size.
// "static void main" must be defined in a public class.
public class Main {
public static void main(String[] args) {
String[] strs = {"abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"};
List<List<String>> list = groupStrings(strs);
for(int i=0; i<list.size(); i++){
System.out.println("List "+(i+1));
List<String> subList = list.get(i);
for(int j=0; j<subList.size(); j++){
System.out.println(subList.get(j));
}
} } public static List<List<String>> groupStrings(String[] strings) {
if(strings == null || strings.length == 0){
return new ArrayList<List<String>>();
} Map<String, List<String>> map = new HashMap<>();
for(int i=0; i<strings.length; i++){
String str = getBase(strings[i]);
if(!map.containsKey(str)){
map.put(str, new ArrayList<String>());
}
map.get(str).add(strings[i]); }
return new ArrayList<List<String>>(map.values()); } public static String getBase(String str){
if(str == null || str.length()==0){
return str;
}
StringBuilder sb = new StringBuilder();
int offset = str.charAt(0) - 'a';
for(int i=0; i<str.length(); i++){
char c = (char) (str.charAt(i)-offset);
if(c < 'a'){
c += 26;
}
sb.append(c); }
return sb.toString();
}
}