This is the 29th day of my participation in the August More Text Challenge

🌟 algorithm problem

You are given an array of strings, and you are asked to combine alphabetic anagram words. The list of results can be returned in any order.

An anagram is a new word created by rearranging the letters of the source word so that all the letters in the source word are used exactly once.

The sample1: Input: STRS = ["eat"."tea"."tan"."ate"."nat"."bat"] Output: [["bat"], ["nat"."tan"], ["ate"."eat"."tea"]]
Copy the code
The sample2: Input: STRS = [""] Output: [[""]]
Copy the code
The sample3: Input: STRS = ["a"] Output: [["a"]]
 
Copy the code
Tip:1 <= strs.length <= 104
0 <= strs[i].length <= 100STRS [I] contains only lowercase lettersCopy the code

🌟 A little thought

I find sometimes it’s not that I can’t do the problem, it’s that I can’t understand the problem and it’s not that hard if you can understand what an allogram is. Put words with the same letter in an array. Ok, so it’s easy to see if they’re all in the same group: [“eat”, “tea”, “tan”, “ate”, “NAT “, “bat”]. You can sort the letters from smallest to largest like aet. Now let’s use hash tables.

🌟 source code and detailed explanation

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
    / / build a hashmap
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            // Sort the STRS words
            Arrays.sort(array);
            // The key that constructs this sequence of words, such as aet, is grouped together if this happens
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return newArrayList<List<String>>(map.values()); }}Copy the code

🌟 interview questions

Q: How do you decide to use HashMap or TreeMap?

The Key values of TreeMap<K,V> require java.lang.Comparable. Therefore, TreeMap iterates in ascending order by default. TreeMap’s implementation is based on a red-black tree structure. It is applicable to traverse keys in natural or custom order.

HashMap<K,V> implements hash hashCode(). The distribution is hash, uniform, and does not support sorting; Data structures are mainly buckets (arrays), linked lists, or red-black trees. Suitable for inserting, deleting, and positioning elements in a Map.

Conclusion You should use TreeMap if you want to get an ordered result (because the order of elements in a HashMap is not fixed). In addition, since HashMap has better performance, we use HashMap most of the time when sorting is not required.

Implementation of HashMap and TreeMap

HashMap: Implemented based on hash tables. The key classes required to be added using HashMap explicitly define hashCode() and equals()[you can override hashCode() and equals()], and you can tune the initial capacity and load factor to optimize the use of HashMap space.

HashMap(): Builds an empty hash image

HashMap(Map M): Build a hash image and add all mappings to image M

HashMap(int initialCapacity): Build an empty hash image with a specific capacity

HashMap(int initialCapacity, float loadFactor): build an empty hash image with a specific capacity and loadFactor

TreeMap: Implemented based on red-black tree. TreeMap has no tuning options because the tree is always in equilibrium.

TreeMap() : Builds an empty image tree

TreeMap(Map M): Builds an image tree and adds all elements in image M

TreeMap(Comparator C): Builds an image tree and sorts keywords using a specific Comparator

TreeMap(SortedMap S): Builds an image tree, adds all mappings in the image tree S, and sorts using the same comparator as the ordered image S