[Algorithm] Determine if two strings are an anagram

The anagram test is commonly used to demonstrate how an naive implementation can perform significant order of magnitudes slower than an efficient one. We’ll also briefly go over why each implementation is not as efficient as you could make it.

A word is an anagram of another if you can rearrange its characters to produce the second word. Here we’ll write multiple increasingly more efficient functions that given two strings determines if they are anagrams of each other.

The best we can do is O(n).

The way is using hashed map, in Javascript or TypeScirpt, we can use Map.

Just simply loop over stirng1 array and set counter for each char. Everytime +1.

Then second loop over string2 array set decrease the counter, if there is a char which is not in the hashed map then two strings are not anagram.

const str1 = "earth";

const str2 = "heart";

/**

 *  Map {

 *     e: 0,

 *     a: 0,

 *     r: 0,

 *     t: 0,

 *     h: 0

 *  }

 *

 */

// Using Map is much easier to set, get, check (has) value

function areAnagrams(str1, str2) {

  const mapping = new Map();

  for (let char of str1.split("")) {

    mapping.set(char, (mapping.get(char) || 0) + 1);

  }

  for (let char of str2.split("")) {

    if (mapping.has(char)) {

      mapping.set(char, mapping.get(char) - 1);

    }

  }

  // Conver Map values to Array

  return Array.from(mapping.values()).every(v => v === 0);

}

const res = areAnagrams(str1, str2);

console.log(res); // true

巴特西

[Algorithm] Determine if two strings are an anagram

最新文章

热门文章