原题链接在这里：https://leetcode.com/problems/group-shifted-strings/
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"],
Return:
[
["abc","bcd","xyz"],
["az","ba"],
["acef"],
["a","z"]
]
Note: For the return value, each inner list‘s elements must follow the lexicographic order.
与Anagrams类似。存HashMap, key是base string.
Time Complexity: O(k*n), k = strings.length, n 是每个string的平均长度.
Space: O(k).
AC Java:
1 public class Solution { 2 public List<List<String>> groupStrings(String[] strings) { 3 List<List<String>> res = new ArrayList<List<String>>(); 4 if(strings == null || strings.length == 0){ 5 return res; 6 } 7 8 HashMap<String, List<String>> hm = new HashMap<String, List<String>>(); 9 Arrays.sort(strings); 10 for(int i = 0; i<strings.length; i++){ 11 String base = getBase(strings[i]); 12 if(!hm.containsKey(base)){ 13 List<String> item = new ArrayList<String>(); 14 item.add(strings[i]); 15 hm.put(base, item); 16 }else{ 17 hm.get(base).add(strings[i]); 18 } 19 } 20 for(Map.Entry<String, List<String>> entry : hm.entrySet()){ 21 res.add(entry.getValue()); 22 } 23 return res; 24 } 25 26 private String getBase(String str){ 27 StringBuilder sb = new StringBuilder(); 28 int diff = str.charAt(0) - ‘a‘; 29 for(char c : str.toCharArray()){ 30 int cDiff = c-‘a‘-diff; 31 if(cDiff < 0){ 32 cDiff+=26; 33 } 34 char newChar = (char)(‘a‘ + cDiff); 35 sb.append(newChar); 36 } 37 return sb.toString(); 38 } 39 }
LeetCode Group Shifted Strings
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/5211776.html