| |
|
Given two strings such as "listen" and "silent", return whether or not they
are valid anagrams of each other. That is, the second word uses the same letters
as the first but potentially in a different order.
One approach is to make a frequency count of the first string, and then iterate
the second string “checking off” each letter from the frequency count of the
first. If we hit a missing letter or reduce the corresponding frequency count to
zero, we know it’s not a valid anagram. If we’re able to check off every letter,
then it is a valid anagram.
function validAnagram(a, b) {
if (a.length !== b.length) {
return false;
}
const freq_a = {};
for (let i = 0; i < a.length; i++) {
freq_a[a[i]] = (freq_a[a[i]] || 0) + 1;
}
for (let i = 0; i < b.length; i++) {
if (!freq_a[b[i]]) {
return false;
}
freq_a[b[i]] -= 1;
}
return true;
}
This algorithm is $O(n)$ as we iterate twice on the number of letters.
View post:
Valid anagram algorithm in JavaScript
|
|
|
|