3ms using rotated string as key of HashMap


  • 0
    Q

    The idea is to rotate all strings to start with 'a' and use this as a signature to search in map

    public class Solution {
        public List<List<String>> groupStrings(String[] strings) {
            HashMap<String, List<String>> map = new HashMap<String, List<String>>();
            ArrayList<String> rotateStr = new ArrayList<String>();
            for(int i = 0; i < strings.length; ++i){
                rotateStr.add(getRotate(strings[i]));
            }
            
            for(int i = 0; i < rotateStr.size(); ++i){
                String sig = rotateStr.get(i);
                if(map.containsKey(sig)){
                    map.get(sig).add(strings[i]);
                }
                else{
                    List<String> tmp = new ArrayList<String>();
                    tmp.add(strings[i]);
                    map.put(sig,tmp);
                }
            }
    
            return new ArrayList<List<String>>(map.values());
        }
        public String getRotate(String s){
            char[] cs = s.toCharArray();
            int dist = cs[0] - 'a';
            if(dist == 0){
                return s;
            }
            for(int i = 0; i < cs.length; ++i){
                int tmp = cs[i] - dist;
                if(tmp < 97){
                    cs[i] = (char)(tmp-97+123);
                }
                else{
                    cs[i] = (char)tmp;
                }
            }
            return new String(cs);
        }
    }

Log in to reply
 

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