[TOC]

Front end with algorithm Leetcode 242. Effective letter heterotopic words

Topic describes

Given two strings s and t, write a function to determine whether t is an alphabetic allotopic of S.

Example 1:

Enter: s ="anagram", t = "nagaram"Output:true
Copy the code

Example 2:

Enter: s ="rat", t = "car"Output:falseNote: You can assume that strings contain only lowercase letters.Copy the code

Advanced: What if the input string contains Unicode characters? Can you adjust your solution to this situation?

242. Valid letter heterotopic words

The profile

There are many ways to judge an allotopic word, including using a hash table, constructing an array of 26 characters, and judging whether a string is equal by sorting the number of occurrences of each character

prompt

Hash, array

parsing

Solution 1: hash table

Hash tables are not so good in this case, but this is the first thing that comes to mind when you see this problem. Build a HashMap and count the number of occurrences of each word in s. Then use the table to determine the number of occurrences of all characters in t. Return false if the number of occurrences is unequal or if there is no such character

Solution 2: array determines the number of occurrences of a character

Construct an array of length 26 and fill it with all zeros. Then, if the character S [I] appears once in S, the number of the subscript position will be incremented once, and the corresponding subscript of t[I] will be subtracted once. If one of the final results is not 0, it means that S and T are not equal

Solution 3: Convert strings

Solution two is a similar idea, but it’s just sorting to see if the strings are equal

algorithm

/** * @param {string} s * @param {string} t * @return {boolean} */
var isAnagram = function (s, t) {
  / / the hash method
  // if (s.length ! == t.length) {return false; }
  // let map = new Map();
  // for (let i = 0; i < s.length; i++) {
  // map.get(s[i]) === undefined ? map.set(s[i], 1) : map.set(s[i], map.get(s[i]) + 1);
  // }
  // for (let j = 0; j < t.length; j++) {
  //   if (map.get(t[j]) > 0) {map.set(t[j], (map.get(t[j])) - 1);} else {return false;}
  // }
  // return true;
  // 26 characters
  if(s.length ! == t.length) {return false; }let kmap = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) { kmap[s[i].charCodeAt(0) - 97] + +; kmap[t[i].charCodeAt(0) - 97]--;
  }
  for (let i = 0; i <26; i++) {if(kmap[i] ! = =0) {return false;}
  }
  return true;
  / / solution to three
  // if (s.length ! == t.length) return false
  // let o = new Array(26).fill(0)
  // for (let i = 0; i < s.length; i++) {
  // o[s[i].charCodeAt(0) - 97]++
  // }
  // let p = new Array(26).fill(0)
  // for (let i = 0; i < t.length; i++) {
  // p[t[i].charCodeAt(0) - 97]++
  // }
  // o = o.toString()
  // p = p.toString()
  // return o === p
};
Copy the code

Pass in the results of the test case run

input:"rat"."art"
output:true
Copy the code

The execution result

Execution time :68 ms, beat 98.28% of users memory consumption in all javascript commits :35.7 MB, beat 87.50% of users in all javascript commitsCopy the code

Making the warehouse

242. Valid letter heterotopic words