249. Group Shifted Strings

Description

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

Iteration

要注意这种case："cz" -> "da"

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> res = new ArrayList<>();
        if (strings == null || strings.length == 0) {
            return res;
        }
        
        for (String s : strings) {
            boolean found = false;
            
            for (List<String> group : res) {
                if (canTransform(s, group.get(0))) {
                    group.add(s);
                    found = true;
                    break;
                }
            }
            
            if (!found) {
                List<String> group = new ArrayList<>();
                group.add(s);
                res.add(group);
            }
        }
        
        return res;
    }
    
    private boolean canTransform(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        
        for (int i = 1; i < s1.length(); ++i) {
            int d1 = (s1.charAt(i) - s1.charAt(i - 1) + 26) % 26;   // tricky
            int d2 = (s2.charAt(i) - s2.charAt(i - 1) + 26) % 26;
            if (d1 != d2) {
                return false;
            }
        }
        
        return true;
    }
}

HashMap, O(nL), S(nL), L is each string length

也可以用Map<String, List<String>>遍历strings，将每个s都变换成以a开头的root，然后将root作为key添加到map中。这样效率更高一点，不用每次都遍历map。

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        if (strings == null || strings.length == 0) {
            return Collections.emptyList();
        }
        
        Map<String, List<String>> groupMap = new HashMap<>();
        for (String s : strings) {
            String base = getBaseStr(s);
            if (!groupMap.containsKey(base)) {
                groupMap.put(base, new ArrayList<>());
            }
            groupMap.get(base).add(s);
        }
        
        List<List<String>> res = new ArrayList<>();
        res.addAll(groupMap.values());
        return res;
    }
    
    private String getBaseStr(String s) {
        if (s == null || s.isEmpty()) {
            return "";
        }
        
        int offset = (s.charAt(0) + 26 - 'a') % 26;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            char base = (char) ((c + 26 - offset) % 26 + 'a');
            sb.append(base);
        }
        
        return sb.toString();
    }
}