This content originally appeared on DEV Community and was authored by Anas Nabil
We say that two strings are anagrams of each other if they have the exact same letters in same quantity of existance of each letter, regardless of non-alphabetic letters and case sensitivity.
Here's an example
// 'hello', 'elloh' -> anagrams
// 'love', 'hate' -> not anagrams
// 'i'm 26 years old' -> 'myeald oirs o' -> anagrams
Well, the Solution is Simple
We just need to remove all non-alphabetic letters first, and turn all letters into lower case.
// 'Hello World!@# ---30..' -> 'helloworld30'
const inputString = 'Hello World!@# ---30..'
inputString.toLowerCase().replace(/[\W_]+/g, ''); // returns 'helloworld30'
\W leaves the underscore, A short equivalent for [^a-zA-Z0-9] would be [\W_]
Then we need to convert string to array, sort the array alphabetically, and then turn it back into a string
// 'hello' -> ['h', 'e', 'l', 'l', 'o'] -> ['e', 'h', 'l', 'l', 'o'] -> ehllo
const inputString = 'Hello World!@# ---30..'
inputString.toLowerCase().replace(/[\W_]+/g, '').split('').sort().join(''); // returns '03dehllloorw'
Here's the final code
const anagrams = (firstInput, secondInput) => {
return (
firstInput
.toLowerCase()
.replace(/[\W_]+/g, '')
.split('')
.sort()
.join('') ===
secondInput
.toLowerCase()
.replace(/[\W_]+/g, '')
.split('')
.sort()
.join('')
);
}
Big O Notation
Time Complexity: O(n * Log n) because we've used sort algorithm
However, a Better solutions do exist, We'll also write another solution
const anagrams = (firstInput, secondInput) => {
firstInput = firstInput.toLowerCase().replace(/[\W_]+/g, '');
secondInput = secondInput.toLowerCase().replace(/[\W_]+/g, '');
if (firstInput.length !== secondInput.length) {
return false;
}
const inputLetterCount = {};
for (let i = 0; i < firstInput.length; i++) {
const currentLetter = firstInput[i];
inputLetterCount[currentLetter] = inputLetterCount[currentLetter] + 1 || 1;
}
for (let i = 0; i < secondInput.length; i++) {
const currentLetter = secondInput[i];
if (!inputLetterCount[currentLetter]) return false;
else inputLetterCount[currentLetter]--;
}
return true;
};
Big O Notation
Time Complexity: O(n)
Space Complexity: O(1)
Happy Coding ❤
This content originally appeared on DEV Community and was authored by Anas Nabil
Anas Nabil | Sciencx (2022-07-23T23:45:00+00:00) JS Anagrams with Big O Notation. Retrieved from https://www.scien.cx/2022/07/23/js-anagrams-with-big-o-notation/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.