This is the 15th day of my participation in the August Text Challenge.More challenges in August

Hello, everybody. Today, I’m going to share with you the next LeetCode medium difficulty problem: letter heterotopic word grouping

The title

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.

Example 1: input: STRS = [" eat ", "tea", "tan", "ate" and "NAT" and "bat"] output: [[" bat "], [" NAT ", "tan"], [" ate ", "eat", "tea"]] example 2: input: STRS = (" ") output: [["]] example 3: input: STRS = [" a "] output: [[" a "]]Copy the code

Analysis of the

1. Ectopic word

1. The length is the same

2. Letters appear at the same frequency

2. Put the same allotopic words in a group

3. Output a two-dimensional array

4. Use all lowercase letters

solution

1. A hashMap + count

2.hasMap+ sort

Solution a:A hashMap + count

1.The first iteration accesses each element2.Use map to store accessed elements,1.Set (key, [...map.get(key), STRS [I]]);2.Set (STRS [I], [STRS [I]]);3.We still use hashMap to compare */var groupAnagrams = function (strs) {
  const map = new Map(a);// The first iteration accesses each element
  for (let i = 0; i < strs.length; i++) {
    let isFindKey = false;
    // Check the map key to see if there are any heterotopic words
    for (const key of map.keys()) {
      if (isAnagram(key, strs[i])) {
        map.set(key, [...map.get(key), strs[i]]);
        isFindKey = true; }}// Create a new map.set(STRS [I], [STRS [I]]);
    if (!isFindKey) {
      map.set(strs[i], [strs[i]]);
    }
  }

  return Array.from(map.values());

  // Compare heterotopic words we still use hashMap to compare heterotopic words
  function isAnagram(s, t) {
    if(s.length ! == t.length)return false;
    const map = new Map(a);for (const char of s) {
      if (map.has(char)) map.set(char, map.get(char) + 1);
      else map.set(char, 1);
    }

    for (const char of t) {
      if(! map.has(char) || map.get(char) ===0) {
        return false;
      } else {
        map.set(char, map.get(char) - 1); }}return true; }};/* Complexity time O(n^2*m) n Array length m Letter length space O(m*n) */
Copy the code

Method 2:hashmap+sort

Train of thought1.The first iteration accesses each element2.Use map to store accessed elements,1.Set (key, [...map.get(key), STRS [I]]);2.Set (STRS [I], [STRS [I]]);3.*/ */ */ */ */ */ */ */ */ */ */ */ */ */ */var groupAnagrams = function (strs) {
  const map = new Map(a);// The first iteration accesses each element
  for (let i = 0; i < strs.length; i++) {
    let isFindKey = false;

    for (const key of map.keys()) {
      // Compare by sort
      if (
        key.length === strs[i].length &&
        [...key].sort().join() === [...strs[i]].sort().join()
      ) {
        map.set(key, [...map.get(key), strs[i]]);
        isFindKey = true; }}// Create a new map.set(STRS [I], [STRS [I]]);
    if (!isFindKey) {
      map.set(strs[i], [strs[i]]);
    }
  }

  return Array.from(map.values());
};

/* Complexity time O(n^2*m) n Array length m Letter length space O(m*n) */
Copy the code

conclusion

This problem inspects the group on the basis of the allotopic word. The solution here is mainly the application of sort and counting for the two solutions of the allotopic word

You can have a look at a column I share (front-end algorithm) where there are more topics about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me to like, thank you very much

If you’re interested in “TS” check out my column (TypeScript common knowledge) and thank you for supporting it

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Some of the materials in this article are from the network. If there is infringement, please contact to delete, [email protected]