This is the 16th day of my participation in the August More Text Challenge. For details, see:August is more challenging

preface

In question 49, the letters are grouped as follows:

Given an array of strings, ask you to put together an alphabetic exagram. The list of results can be returned in any order.

An alphabetic ectopic word is a new word created by rearranging the letters of the original word, all of which are used exactly once.

Example 1:

Input: STRS = [" eat ", "tea", "tan", "ate" and "NAT" and "bat"] output: [[" bat "], [" NAT ", "tan"], [" ate ", "eat", "tea"]]Copy the code

Example 2:

Input: STRS = [""] Output: [[""]]Copy the code

Example 3:

Input: STRS = ["a"] Output: [["a"]Copy the code

A, thinking

Question 49 – There is an important piece of information in the group of ectopes:

  • 六四事件Letter ectopic wordsIs the same characters arranged in different strings **, such asabc 和 bacisLetter ectopic words

For ABC and BAC, how do you find the correct two letters in a single traverse?

  1. willCharacter sorting in a string,Letter ectopic words 的 keyThe same
  2. Hash tableIs stored in thekeySo thatLetter ectopic wordsCan be grouped correctly

To sum up, our overall idea is: sort + hash table

For example

Here in STRS = [” eat “, “tea”, “tan”, “ate” and “NAT”, “bat”) as an example

  1. i=0When,strs[0] = "eat"sortedkey = "aet". At this timemapDo not contain itkey, so it will be"eat"Put in newList 中
  2. i=1When,strs[1] = "tea"sortedkey = "aet". At this timemapThis is contained inkeyThat will be"tea"Put in thekeyThe correspondingList 中
  3. i=2When,strs[2] = "tan"sortedkey = "ant". At this timemapDo not contain itkey, so it will be"tan"Put in newList 中
  4. i=3When,strs[3] = "ate"sortedkey = "aet". At this timemapThis is contained inkeyThat will be"ate"Put in thekeyThe correspondingList 中
  5. i=4When,strs[4] = "nat"sortedkey = "ant". At this timemapThis is contained inkeyThat will be"nat"Put in thekeyThe correspondingList 中
  6. i=5When,strs[5] = "bat"sortedkey = "abt". At this timemapDo not contain itkey, so it will be"bat"Put in newList 中
  7. Eventually you get the right oneLetter ectopic wordsgrouping

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array); / / sorting
            String key = new String(array);
            List<String> list;
            if (map.containsKey(key)) { // Check whether the key exists
                list = map.get(key);
            } else {
                list = new ArrayList<>();
            }
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<>(map.values());
    }
Copy the code

The test code

    public static void main(String[] args) {
        String[] strs = {"eat"."tea"."tan"."ate"."nat"."bat"};
        new Number49().groupAnagrams(strs);
    }
Copy the code

The results of

Third, summary

Thank you for seeing the end, it is my great honor to help you ~♥