249. Group Shifted Strings

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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 non-empty 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"]
]

Code

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        HashMap<String, List<String>> map = new HashMap<>();
        for(String s : strings) {
            String key = helper(s);
            if(!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }

            map.get(key).add(s);
        }

        List<List<String>> res = new ArrayList<>();
        for(List<String> l : map.values()) {
            res.add(l);
        }

        return res;
    }

    private String helper(String s) {
        int dis = s.charAt(0) - 'a';

        char[] carr = new char[s.length()];
        carr[0] = 'a';

        for(int i = 1; i < s.length(); i++) {
            char c = (char)(s.charAt(i) - dis);
            if(c < 'a') {
                c += 26;
            }

            carr[i] = c;
        }

        return new String(carr);
    }
}

class Solution:
    def groupStrings(self, strings: List[str]) -> List[List[str]]:
        map = defaultdict(list)

        def getKey(s:str):
            d = ord(s[0]) - ord('a')

            r = ""
            for c in s:
                dd = ord(c) - d
                if dd < ord('a'):
                    dd += 26
                r += chr(dd)

            return r

        for s in strings:
            key = getKey(s)
            map[key].append(s)

        return map.values()