Problem Statement
Determine if two strings are anagrams (contain the same characters in any order).
Example Inputs
- Input:
"listen", "silent"
- Input:
"triangle", "integral"
- Input:
"apple", "papel"
- Input:
"hello", "bello"
JavaScript Method - Using Only String Methods
Approach
To determine if two strings are anagrams, we can sort both strings and then check if they are identical. If they are, they contain the same characters in the same quantities, so they are anagrams.
Steps
- Convert both strings to lowercase to handle case insensitivity.
- Use
.split('').sort().join('') to sort both strings.
- Compare the sorted versions of the strings.
- If they are equal, the strings are anagrams; otherwise, they are not.
Time & Space Complexity
- Time Complexity: O(n log n), where n is the length of the strings, due to sorting.
- Space Complexity: O(n), as new strings are created when sorting.
Code Snippet
Dry Run
Example input: "listen", "silent"
- Convert both to lowercase:
"listen" and "silent"
- Sort:
"listen".split('').sort().join('') → "eilnst""silent".split('').sort().join('') → "eilnst"
- Compare
"eilnst" === "eilnst" → true
Final output: true
Alternative Approach - Using Frequency Map
Approach
Instead of sorting, we can use a frequency map to count each character in both strings and compare the maps. If both maps match, the strings are anagrams.
Steps
- Check if both strings have the same length. If not, return
false.
- Initialize an object to count character frequencies for the first string.
- Loop through the first string and populate the frequency map.
- Loop through the second string, decrementing the count for each character in the frequency map.
- If any character count is zero or any character is missing, return
false.
- If all counts are zero at the end, return
true.
Time & Space Complexity
- Time Complexity: O(n), as we iterate through each string once.
- Space Complexity: O(k), where k is the number of unique characters.
Code Snippet
Dry Run
Example input: "listen", "silent"
- Initialize
frequency = {} for "listen":
l → { l: 1 }i → { l: 1, i: 1 }s → { l: 1, i: 1, s: 1 }t → { l: 1, i: 1, s: 1, t: 1 }e → { l: 1, i: 1, s: 1, t: 1, e: 1 }n → { l: 1, i: 1, s: 1, t: 1, e: 1, n: 1 }
- Loop through
"silent", decrementing counts:
s → { l: 1, i: 1, s: 0, t: 1, e: 1, n: 1 }i → { l: 1, i: 0, s: 0, t: 1, e: 1, n: 1 }l → { l: 0, i: 0, s: 0, t: 1, e: 1, n: 1 }e → { l: 0, i: 0, s: 0, t: 1, e: 0, n: 1 }n → { l: 0, i: 0, s: 0, t: 1, e: 0, n: 0 }
- Final output:
true
Complexity Analysis
JavaScript Method (Using String Methods)
- Time Complexity: O(n log n)
- Space Complexity: O(n)
Alternative Approach (Using Frequency Map)
- Time Complexity: O(n)
- Space Complexity: O(k)
Conclusion
Determining if two strings are anagrams can be done by sorting or by using a frequency map. Sorting provides a simple approach, while the frequency map offers better time complexity for longer strings.