Leetcode 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:
|
1 |
"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:
|
1 2 3 4 5 6 |
[ ["abc","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"] ] |
Note: For the return value, each inner list’s elements must follow the lexicographic order.
A better example:
[“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” is a group shifted strings.
We can see a pattern among string of one group, the difference between consecutive characters for all character of string are equal. As in above example take acd, dfg and mop
a c d -> 2 1
d f g -> 2 1
m o p -> 2 1
Since the differences are same, we can use this to identify strings that belong to same group. The idea is to form a string of differences as key. If a string with same difference string is found, then this string also belongs to same group. For example, above three strings have same difference string, that is “21”.
Java Solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
public List<List<String>> groupStrings(String[] strings) { List<List<String>> result = new ArrayList<List<String>>(); HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>(); for(String s: strings){ char[] arr = s.toCharArray(); if(arr.length>0){ int diff = arr[0]-'a'; for(int i=0; i<arr.length; i++){ if(arr[i]-diff<'a'){ arr[i] = (char) (arr[i]-diff+26); }else{ arr[i] = (char) (arr[i]-diff); } } } String ns = new String(arr); if(map.containsKey(ns)){ map.get(ns).add(s); }else{ ArrayList<String> al = new ArrayList<String>(); al.add(s); map.put(ns, al); } } for(Map.Entry<String, ArrayList<String>> entry: map.entrySet()){ Collections.sort(entry.getValue()); } result.addAll(map.values()); return result; } |
