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.


For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"], 
A solution is:

Thought Process

  1. Hash Table - Normalized Key
    1. Using the first character as gauge and make the first character 'a', and normalize the rest of characters accordingly
    2. Time complexity O(nw), where n is number of word, w is the average width of the word
    3. Space complexity O(nw)


class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> res = new ArrayList<>();
        if (strings == null || strings.length == 0) return res;
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strings) {
            String key = normalize(str);
            if (!map.containsKey(key)) map.put(key, new ArrayList<>());
        return res;

    private String normalize(String s) {
        if (s.length() == 0 || s.charAt(0) == 'a') return s;
        char[] chars = s.toCharArray();
        int diff = chars[0] - 'a';
        for (int i = 0; i < chars.length; i++) {
            chars[i] -= diff;
            if (chars[i] < 'a') chars[i] += 26;
        return String.valueOf(chars);


results matching ""

    No results matching ""