0249. Group Shifted Strings

https://leetcode.com/problems/group-shifted-strings

Description

We can shift a string by shifting each of its letters to its successive letter.

• For example, "abc" can be shifted to be "bcd".

We can keep shifting the string to form a sequence.

• For example, we can keep shifting "abc" to form the sequence: "abc" -> "bcd" -> ... -> "xyz".

Given an array of strings strings, group all strings[i] that belong to the same shifting sequence. You may return the answer in any order.

Example 1:

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

Example 2:

**Input:** strings = ["a"]
**Output:** [["a"]]

Constraints:

• 1 <= strings.length <= 200

• 1 <= strings[i].length <= 50

• strings[i] consists of lowercase English letters.

ac

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> res = new ArrayList<List<String>>();

        Map<Integer, List<List<String>>> map = new HashMap<Integer, List<List<String>>>();

        // group by len
        for (String s : strings) {
            int len = s.length();
            if (!map.containsKey(len)){
                map.put(len, new ArrayList<List<String>>());
                List<String> tmpList = new ArrayList<String>();;
                tmpList.add(s);
                map.get(len).add(tmpList);
            } else {
                boolean added = false;
                for (List<String> list : map.get(len)) {
                    if (same(list.get(0), s)) {
                        list.add(s);
                        added = true;
                        break;
                    }
                }
                if (!added) {
                    List<String> tmpList = new ArrayList<String>();
                    tmpList.add(s);
                    map.get(len).add(tmpList);
                }
            }
        }

        // add to result
        for (List<List<String>> lists : map.values()) {
            for (List<String> list : lists) res.add(list);
        }

        return res;
    }

    private boolean same(String s1, String s2) {
        int diff = (s2.charAt(0) - s1.charAt(0) + 26) % 26;
        for (int i = 1; i < s1.length(); i++) {
            int num1 = s1.charAt(i) - 'a';
            int num2 = s2.charAt(i) - 'a';
            if ( (num1 + diff) % 26 != num2 ) return false;
        }
        return true;
    }
}

ac2: transform every word back to base status

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> res = new ArrayList<List<String>>();

        Map<String, List<String>> map = new HashMap<String, List<String>>();

        for (String s : strings) {
            // get base key
            String key = "";
            int diff = s.charAt(0) - 'a';
            for (int i = 0; i < s.length(); i++) {
                char c = (char) (s.charAt(i) - diff);
                if (c < 'a') c += 26;
                key += c;
            }

            // add to map
            if (!map.containsKey(key)) map.put(key, new ArrayList<String>());
            map.get(key).add(s);
        }

        // add to result return
        for (List<String> list : map.values()) {
            res.add(list);
        }

        return res;
    }
}