My Concise JAVA Solution


  • 67
    S
    public class Solution {
        public List<List<String>> groupStrings(String[] strings) {
            List<List<String>> result = new ArrayList<List<String>>();
            Map<String, List<String>> map = new HashMap<String, List<String>>();
            for (String str : strings) {
                int offset = str.charAt(0) - 'a';
                String key = "";
                for (int i = 0; i < str.length(); i++) {
                    char c = (char) (str.charAt(i) - offset);
                    if (c < 'a') {
                        c += 26;
                    }
                    key += c;
                }
                if (!map.containsKey(key)) {
                    List<String> list = new ArrayList<String>();
                    map.put(key, list);
                }
                map.get(key).add(str);
            }
            for (String key : map.keySet()) {
                List<String> list = map.get(key);
                Collections.sort(list);
                result.add(list);
            }
            return result;
        }
    }

  • 11
    H

    Similar idea, thanks for sharing!

    public class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> result = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        for(String s: strings){
            String key = getBitMap(s);
            if(!map.containsKey(key))
                map.put(key, new ArrayList<String>());
            map.get(key).add(s);
        }
        for(String key: map.keySet()){
            List<String> list = map.get(key);
            Collections.sort(list);
            result.add(list);
        }
        return result;
    }
    private String getBitMap(String s){
        int[] arr = new int[s.length()];
        arr[0] = 0;
        for(int i = 1; i < s.length(); i++){
            arr[i] = s.charAt(i)-s.charAt(0) < 0? 
                     ((s.charAt(i)-s.charAt(0))%26 + 26): (s.charAt(i)-s.charAt(0));
        }
        return Arrays.toString(arr);
    }
    

    }


  • 0
    M

    I think you should add some tag when you append the numbers, or [12, 1] and [1, 21] will be treated as the same key.


  • 2

    Nice! Two suggestions: (1) Use a StringBuilder instead of key += c; (2) Abstract key encoding logic into one function for better readability.


  • 3
    Z

    Just another similar version.

        public List<List<String>> groupStrings(String[] ss) {
        Map<String, List<String>> map = new HashMap<>();
        
        for(String s: ss){
            String key = getTag(s);
            List<String> value = map.get(key);
            if(value == null){
                value = new ArrayList<>();
                map.put(key, value);
            }
            
            value.add(s);
        }
            
        List<List<String>> ret = new ArrayList<>();
        for(List<String> lst: map.values()){
            Collections.sort(lst); // dont forget to sort.
            ret.add(lst);
        }
            
        return ret;
    }
    
    String getTag(String s){
        int diff = (int)s.charAt(0) - (int)'a';
        
        StringBuilder sb = new StringBuilder();
        for(char c: s.toCharArray())
            sb.append((c+26-diff)%26);
        
        return sb.toString();
    }

  • 0
    G

    I would use just simple char[] (instead of StringBuilder) - as the length of the string is known in advance. Then construct new String(chars).


  • 13
    8

    More readable one...

    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> ret = new ArrayList<List<String>>();
        HashMap<String, List<String>> map = new HashMap<String, List<String>>();
        for(String s : strings) {
            String key = "";
            for(int i = 1; i < s.length(); i++) {
                int offset = s.charAt(i) - s.charAt(i - 1);
                key += offset < 0 ? offset + 26 : offset;
            }
            if(!map.containsKey(key)) map.put(key, new ArrayList<String>());
            map.get(key).add(s);
        }
        for(List<String> ss : map.values()) {
            Collections.sort(ss);
            ret.add(ss);
        }
        return ret;
    }

  • 0
    V

    It treats the diff as a char, not a integer.


  • 3
    H
    public List<List<String>> groupStrings(String[] strings) {
            List<List<String>> res = null;
            Map<String,List<String>> map = new HashMap<>();
            
            for(String string: strings){
                int shift = string.charAt(0) - 'a';
                StringBuilder key = new StringBuilder();
                
                for(int i=0;i<string.length();i++){
                    key.append((char)(string.charAt(i)+26-shift)%26);
                }
                
                String k = key.toString();
                if(!map.containsKey(k)) map.put(k,new ArrayList<String>());
                map.get(k).add(string);
            }
            res = new ArrayList<>(map.values());
            return res;
        }
    

  • 0
    I

    if you have empty string, this would not work ,right?


  • 3
    L

    Ugh, I got asked this question by Google and I did it in O(n^2). Needless to say I didn't proceed to the next round.


  • 0
    I

    @lekzeey

    I am sorry to hear that bro. But most of the solutions appeared in the discussion board are O(N^2).


  • 2

    @ZZJJ Similar solution. But why do we need to sort the values. I didn't sort but still got AC. Runtime is 7ms.

        public List<List<String>> groupStrings(String[] strings) {
            Map<String,List<String>> map = new HashMap<String,List<String>>();
            for(int i=0;i<strings.length;i++){
                String word = shift(strings[i]);
                if(!map.containsKey(word)){
                    map.put(word,new ArrayList<String>());
                }
                map.get(word).add(strings[i]);
            }
            return new ArrayList(map.values());
        }
        public String shift(String word){
            if(word==null||word.length()==0)
                return word;
            char[] chArray = word.toCharArray();
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<chArray.length-1;i++){
                sb.append(((chArray[i+1]-chArray[i])<0?chArray[i+1]-chArray[i]+26:chArray[i+1]-chArray[i])+"");
            }
            return sb.toString();
        }
    

  • 0
    A

    What is the time complexity of this solution ?


  • 0
    V

    @lekzeey I hate to say it, but I think you messed up somewhere else. I don't think this question can be done in O(n) time... my O(n^2) solution beats 98% of python solutions so... how can they expect better? Maybe some other criteria you messed up :/

    A side point, I agree @Derek_Han. Sorting is not necessary for this question. Only slows down solution time.


  • 0
    public class Solution {
        public List<List<String>> groupStrings(String[] strings) {
            List<List<String>> res = new ArrayList();
            int n = strings.length;
            Map<Integer, List<String>> map = new HashMap();
            boolean[] vis = new boolean[n];
            
            for (int i = 0; i < n; i++) {
                if (vis[i]) continue;
                vis[i] = true;
                List<String> list = new ArrayList();
                list.add(strings[i]);
                for (int j = 1; j < n; j++) {
                    if (vis[j]) continue;
                    if (isMatch(strings[i], strings[j])) {
                        list.add(strings[j]);
                        vis[j] = true;
                    }
                }
                res.add(list);
            }
            return res;
        }
        
        private boolean isMatch(String a, String b) {
            if (a.length() != b.length()) return false;
            if (a.length() == 1) return true;
            int len = a.length();
            int i = 1;
            int degree = (a.charAt(0) - b.charAt(0) + 26) % 26;
            while (i < len) {
                if (degree != (a.charAt(i) - b.charAt(i) + 26) % 26) return false;
                i++;
            }
            return true;
        }
    }
    

  • 0

    @huaying2 Same as yours except use of char array instead of StringBuilder.
    At first, I shift each char by: ch[i] = (char) ('a' + (ch[i] - 'a' + (26 - shift)) % 26); which seems not necessary.
    But I think we forget to sort before return, right?

        public List<List<String>> groupStrings(String[] strs) {
            Map<String, List<String>> group = new HashMap<>();
            for (String str : strs) {
                char[] c = str.toCharArray();
                for (int i = 0, shift = c[0] - 'a'; i < c.length; i++)
                    c[i] = (char) ((c[i] + 26 - shift) % 26);
    
                String key = String.valueOf(c);
                if (!group.containsKey(key))
                    group.put(key, new ArrayList<>());
                group.get(key).add(str);
            }
            return new ArrayList<>(group.values());
        }
    

  • 0

    Actually I wonder the function of +26 in the c[i] = (char) ((c[i] + 26 - shift) % 26); Seems everybody uses it but it can still pass the OJ without adding 26.
    Plus, can anyone clarify the workflow of % operation here? I think it is for handling situations like 'y'+2->'a', but it's not easily visualizable.


  • 1

    @OpMaker

    In the problem statement, it says Given a list strings which contains only lowercase alphabets.

    In this case, +26 isn't necessary, as c[i] is always > 96.

    But, it'll cause problems if characters are in a wider range.


  • 0

    A sligth improvement, use addAll() to add collections of values at the end into the result and return, it will be much easier!

        public List<List<String>> groupStrings(String[] strings) {
            List<List<String>> result = new ArrayList<List<String>>();
            Map<String, List<String>> map = new HashMap<String, List<String>>();
            
            for (String s: strings) {
                //create key for the string, make first letter into a
                if (s.length() == 0) continue;
                int offset = s.charAt(0) - 'a';
                String key = "";
                for (int i = 0; i < s.length(); i++) {
                    char c = (char) (s.charAt(i) - offset);
                    if (c < 'a') c += 26; //rotate
                    key += c; //apend the c
                }
                
                if (!map.containsKey(key)) {
                    map.put(key, new ArrayList<String>());
                }
                map.get(key).add(s);
            }
            result.addAll(map.values());
            return result;
        }
    ```

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.