Concise 10-lines JAVA Solution with explanation


  • 21

    Explanation

    The basic idea is to set a key for each group: the sum of the difference between the adjacent chars in one string. Then we can easily group the strings belonging to the same shifting sequence with the same key. The code is as the following:

    public List<List<String>> groupStrings(String[] strs) {
    	HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        Arrays.sort(strs);    	
    	for (String s : strs) {
    		String key = "";
    		for (int i = 1; i < s.length(); i++) 
    			key += String.format("%2d", (s.charAt(i) - s.charAt(i-1) + 26) % 26);//Difference from the previous char.
    		if (!map.containsKey(key)) map.put(key, new ArrayList<String>());
    		map.get(key).add(s);    		
    	} 
    	return new ArrayList<List<String>>(map.values());
    }

  • 1
    Y

    This code section is really concise and smart, however the time complexity is not good, it reaches almost 112ms, can it be improved?


  • 0
    Y
    This post is deleted!

  • 0
    Q
    This post is deleted!

  • 0

    @Yun.Hu agreed, the idea is correct, but execution could be improved. The sort seems unnecessary (am I missing something?) and the construction of the key would be better served using a char array to avoid iterative building of the string key.

    I came up with virtually the same approach with the mentioned changes.

        public IList<IList<string>> GroupStrings(string[] strings) 
        {
            Dictionary<string, IList<string>> map = new Dictionary<string, IList<string>>();
            foreach (string s in strings)
            {
                string key = GetKey(s);
                if (!map.ContainsKey(key)) map[key] = new List<string>();
                map[key].Add(s);
            }
            
            IList<IList<string>> lists = new List<IList<string>>();
            foreach (string key in map.Keys)
            {
                lists.Add(map[key]);
            }
            return lists;
        }
        
        public string GetKey(string s)
        {
            char[] chars = new char[s.Length];
            for (int i = 0 ; i < s.Length; i++)
            {
                chars[i] = (char)((26 + s[i] - (s[0] - 'a')) % 26) ;
            }
            return new string(chars);
        }
    

  • 0

    I got a question for this solution.
    Given the test cases

    ["ad", "abc"]
    

    The cumulative differences both are 3

    d - a => 3
    b-a + c-b => 3
    

    How can you deal with this scenario?


  • 2

    Thanks. It was your solution that made me start to understand. :)

    FOr others who still don't understand,

    Basically we need to form some sort of key for each word to group them. (Remember the idea of group all anagrams?)

    Consider acf and pru. Now notice the differnce between each characters.
    acf = 0->2->3, and pru = 0->2->3. So these two form same group. So in this case, you can simply use integers ASCII difference to form key.

    Now consider corner case, az and ba, where az = 0->25 and ba = 0->-1. When it goes negative, just make it positive(rotate or mod equivalent) by adding 26. So it becomes, ba = 0->25, which forms same group.

    public List<List<String>> groupStrings(String[] strings) {
        Map<String, List<String>> map = new HashMap<>();
    
        for(String s : strings) {
            String key = getKey(s);
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(s);
            map.put(key, list);
        }
        return new ArrayList<>(map.values());
    }
    
    private String getKey(String s) {
        char[] chars = s.toCharArray();
        String key = "";
        for(int i = 1; i < chars.length; i++) {
            int diff = chars[i] - chars[i-1];
            key += diff < 0 ? diff + 26 : diff;
            key += ",";
        }
        return key;
    }

Log in to reply
 

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