Distinct way to solve this problem: calculate weight of every word, then use hashmap to group them


  • 0
    X

    My solution is of course not the best, not the most concise. However, I am trying to use a different way to solve this problem. It takes 6ms to solve this problem.

    I am trying to calculate weight of every String, then use hashmap to group them.

    Weight: all number gap between two consecutive chars of one String. I use "," to separate them.
    For example,
    abc = 'b-a','c-b' = 1,1
    xyz = 'y-x','z-y' = 1,1
    HashMap will make "1,1" as the key to group them.
    If you see the gap is negative, just simply +=26 to make it become positive
    For example,
    za = 'a-z' = -25+26 = 1
    ab = 'b-a' = 1

    You will notice that my weight can only be calculated when str has at least two chars. We just need to make single char word in one same group List. Because it can onlly be "a" ~ "z", all belong to the same shifting group. Here I am using singleList to handle.

    The time complexity is O(M*N), M is average length of every word, N is the length of strings, because we go through all chars of word to calculate this weight. Space complexity is O(N), N is length of strings

    Here is my code:

      public class Solution {
       public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> result = new ArrayList<List<String>>();
        if(strings == null || strings.length == 0) return result;
        
        List<String> singleList = new ArrayList<String>();
        HashMap<String, List<String>> map = new HashMap<String, List<String>>();
        for(String str:strings){
            //Follow the question, 
            //seems there are no null or "" in the array, so I don't handle it.
            if(str.length() == 1) singleList.add(str); //"a"~"z" are same group
            else{ // calculate the weight of str whose length is larger than 1
                String weight = calculateWeight(str);
                if(map.containsKey(weight)){
                    map.get(weight).add(str);
                } else{
                    List<String> list = new ArrayList<String>();
                    list.add(str);
                    map.put(weight,list);
                }
            }
        }
        if(singleList.size() !=0){ 
          //If single List is not empty, add into result.
            result.add(singleList);
        }
        
        for(String k: map.keySet()){
            result.add(map.get(k));
        }
        return result;
    }
    
    public String calculateWeight(String str){
        StringBuffer sb = new StringBuffer();
        char[] arr = str.toCharArray();
        int i = 0;
        int j = 1;
        while(j < str.length()){
            if(sb.length() != 0) {
                sb.append(","); //Adding separator
            }
            int gap = arr[j]-arr[i]; //Use two pointer to calculate gap
            if(gap < 0) gap+=26; //Deal with negative gap
            sb.append(gap);
            i++;
            j++;
        }
        return sb.toString();
    }
    

    }


Log in to reply
 

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