Radix sort solution


  • 0
    public List<List<String>> groupStrings(String[] strings) {
        //one character radix sort
        int[] bu=new int[26];
        for(int i=0;i<strings.length;i++)
        {
            bu[strings[i].charAt(0)-'a']++;
        }
        for(int i=1;i<26;i++)
        bu[i]+=bu[i-1];
        
        String[] ss=new String[strings.length];
        for(int i=strings.length-1;i>=0;i--)
        {
            ss[--bu[strings[i].charAt(0)-'a']]=strings[i];
        }
        
        //the same idea as what you have
        HashMap<String,List<String>> hm=new HashMap<String,List<String>>();
        for(int i=0;i<strings.length;i++)
        {
            String cur=ss[i];
            StringBuilder token=new StringBuilder();
            if(cur.length()==1) token.append('-');
            else
            {
                for(int j=1;j<cur.length();j++)
                {
                    token=token.append((cur.charAt(j)-cur.charAt(j-1)+26)%26);
                }
            }
            if(hm.containsKey(token.toString())) hm.get(token.toString()).add(cur);
            else
            {
                List<String> tmp=new ArrayList<>();
                tmp.add(cur);
                hm.put(token.toString(),tmp);
            }
        }
        return new ArrayList<List<String>>(hm.values());
    }

Log in to reply
 

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