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


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 asabcbacisLetter 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 wordskeyThe 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<>();
            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 ~♥