[LeetCode 249] Group Shifted Str

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.

Example:

Input: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
Output: 
[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]

Solution: HashTable + Base String

1. 题目需要找互为shift string的字符串，将其group到一起。那么肯定是用HashTable <String, List<String>>来完成。但是怎么判断字符串是否是shift String呢？？？
2. 对每个String，都找其base String，即没有shift之前的String。 看个例子，abc和bcd。
   • 首先假设每个String都是由a开始的。如果首字符不是a，那么可以算出它与a之间的diffLen
   • 再遍历该字符串，对每个字符根据diffLen，将其反向shift回base String。current character - 'a' - diffLen + 'a'
   • 例如abc, shift以后还是abc。 但是bcd: ===> shift ===> abc 。所以归为一类
   • 但是，有一特殊情况需要处理，即["az","ba"]，可以看出字符是循环的。所以为了处理 减去deifflen为负数的情况， 反向shift需处理为 （current character - 'a' - diffLen + 26) % 26 + 'a'

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> result = new ArrayList<> ();
        if (strings == null || strings.length == 0)
            return result;
        
        
        //1. get hashmap
        Map<String, List<String>> tracker = new HashMap<> ();
        
        for (String str : strings) {
            String baseStr = getBaseString (str);
            List<String> group = tracker.getOrDefault (baseStr, new ArrayList<String> ());
            group.add (str);
            tracker.put (baseStr, group);
        }
        
        for (String key : tracker.keySet ()) {
            Collections.sort (tracker.get (key));
        }
        
        return new ArrayList<> (tracker.values ());
    }
    
    public String getBaseString (String str) {
        StringBuilder result = new StringBuilder ();
        if (str == null || str.length () == 0) {
            return "";
        }
        
        int shiftedLen = str.charAt (0) - 'a';
        
        for (int i = 0; i < str.length (); i++) {
            // handle "za, shiftedLen = z -a = 25; when visiting a, then currentLen = a - a - 25 = -25 
            // needs to convert into a character in a- z ===> b; therefore it should be (- 25 + 26) % 26 == 1
            int currentShiftLen = ((str.charAt (i) - 'a' - shiftedLen) + 26) % 26;    
            result.append ('a' + currentShiftLen);
        }
        
        return result.toString ();
    }
}