Anagrams are fascinating because they involve rearranging letters to form different words or phrases. For instance, “listen” and “silent” are classic examples of anagrams. Determining whether two strings are anagrams can be approached in various ways. In this blog post, we’ll delve into methods using sorting and dictionaries for Python, JavaScript, C, and C++.
Method 1: Using Sorting
Python Implementation
One effective method for checking if two strings are anagrams is by sorting both strings and comparing them. If the sorted versions of the strings match, they are anagrams. Here’s how you can implement this in Python:
def are_anagrams_sort(s1, s2):
return sorted(s1) == sorted(s2)
# Example usage
print(are_anagrams_sort("listen", "silent")) # Output: True
print(are_anagrams_sort("hello", "world")) # Output: FalseExplanation:
- Sorting: We use Python’s built-in sorted() function to sort the characters in each string.
- Comparison: If the sorted lists of characters are identical, the original strings are anagrams.
This approach is simple and takes advantage of Python’s efficient sorting algorithms. However, its time complexity is (O(n \log n)), where (n) is the length of the strings.
JavaScript Implementation
Here’s how you can achieve the same result in JavaScript:
function areAnagramsSort(s1, s2) {
return s1.split('').sort().join('') === s2.split('').sort().join('');
}
// Example usage
console.log(areAnagramsSort("listen", "silent")); // Output: true
console.log(areAnagramsSort("hello", "world")); // Output: falseExplanation:
- Sorting: We split the strings into arrays of characters, sort them, and then join them back into strings.
- Comparison: The equality operator checks if the sorted strings are the same.
This method is similar to Python’s sorting approach and is easy to implement.
Method 2: Using a Dictionary (or Hash Map)
Python Implementation
Another method is to use dictionaries to count the frequency of each character. If the character counts match, the strings are anagrams:
def are_anagrams_dict(s1, s2):
if len(s1) != len(s2):
return False
freq1 = {}
freq2 = {}
for char in s1:
freq1[char] = freq1.get(char, 0) + 1
for char in s2:
freq2[char] = freq2.get(char, 0) + 1
return freq1 == freq2
# Example usage
print(are_anagrams_dict("listen", "silent")) # Output: True
print(are_anagrams_dict("hello", "world")) # Output: FalseExplanation:
- Frequency Counting: We count occurrences of each character in both strings using dictionaries.
- Comparison: If the frequency dictionaries match, the strings are anagrams.
This method has a time complexity of (O(n)), where (n) is the length of the strings, making it more efficient for large strings.
JavaScript Implementation
Here’s how you can implement the dictionary-based approach in JavaScript:
function areAnagramsDict(s1, s2) {
if (s1.length !== s2.length) {
return false;
}
const freq1 = {};
const freq2 = {};
for (const char of s1) {
freq1[char] = (freq1[char] || 0) + 1;
}
for (const char of s2) {
freq2[char] = (freq2[char] || 0) + 1;
}
for (const char in freq1) {
if (freq1[char] !== freq2[char]) {
return false;
}
}
return true;
}
// Example usage
console.log(areAnagramsDict("listen", "silent")); // Output: true
console.log(areAnagramsDict("hello", "world")); // Output: falseExplanation:
- Frequency Counting: We count the characters in each string using objects.
- Comparison: We then compare the frequency counts to determine if the strings are anagrams.
C Implementation
Using Sorting
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int are_anagrams_sort(const char *s1, const char *s2) {
char sorted1[1000], sorted2[1000];
strcpy(sorted1, s1);
strcpy(sorted2, s2);
int len1 = strlen(sorted1);
int len2 = strlen(sorted2);
if (len1 != len2) return 0;
// Sorting
qsort(sorted1, len1, sizeof(char), (int (*)(const void *, const void *))strcmp);
qsort(sorted2, len2, sizeof(char), (int (*)(const void *, const void *))strcmp);
return strcmp(sorted1, sorted2) == 0;
}
int main() {
printf("Are anagrams: %d\n", are_anagrams_sort("listen", "silent")); // Output: 1 (true)
printf("Are anagrams: %d\n", are_anagrams_sort("hello", "world")); // Output: 0 (false)
return 0;
}Explanation:
- Sorting: We copy the strings and use qsort to sort them.
- Comparison: We compare the sorted strings.
Using a Frequency Array
#include <stdio.h>
#include <string.h>
int are_anagrams_dict(const char *s1, const char *s2) {
int freq1[256] = {0};
int freq2[256] = {0};
int len1 = strlen(s1);
int len2 = strlen(s2);
if (len1 != len2) return 0;
for (int i = 0; i < len1; i++) {
freq1[(unsigned char)s1[i]]++;
freq2[(unsigned char)s2[i]]++;
}
for (int i = 0; i < 256; i++) {
if (freq1[i] != freq2[i]) return 0;
}
return 1;
}
int main() {
printf("Are anagrams: %d\n", are_anagrams_dict("listen", "silent")); // Output: 1 (true)
printf("Are anagrams: %d\n", are_anagrams_dict("hello", "world")); // Output: 0 (false)
return 0;
}Explanation:
- Frequency Counting: We use arrays to count occurrences of each character.
- Comparison: We compare the frequency arrays.
C++ Implementation
Using Sorting
#include <iostream>
#include <algorithm>
bool areAnagramsSort(const std::string &s1, const std::string &s2) {
std::string sorted1 = s1;
std::string sorted2 = s2;
if (sorted1.length() != sorted2.length()) return false;
std::sort(sorted1.begin(), sorted1.end());
std::sort(sorted2.begin(), sorted2.end());
return sorted1 == sorted2;
}
int main() {
std::cout << "Are anagrams: " << areAnagramsSort("listen", "silent") << std::endl; // Output: 1 (true)
std::cout << "Are anagrams: " << areAnagramsSort("hello", "world") << std::endl; // Output: 0 (false)
return 0;
}Explanation:
- Sorting: We use std::sort to sort the strings.
- Comparison: We compare the sorted strings.
Using a Frequency Map
#include <iostream>
#include <unordered_map>
bool areAnagramsDict(const std::string &s1, const std::string &s2) {
if (s1.length() != s2.length()) return false;
std::unordered_map<char, int> freq1;
std::unordered_map<char, int> freq2;
for (char ch : s1) freq1[ch]++;
for (char ch : s2) freq2[ch]++;
return freq1 == freq2;
}
int main() {
std::cout << "Are anagrams: " << areAnagramsDict("listen", "silent") << std::endl; // Output: 1 (true)
std::cout << "Are anagrams: " << areAnagramsDict("hello", "world") << std::endl; // Output: 0 (false)
return 0;
}Explanation:
- Frequency Counting: We use std::unordered_map to count character frequencies.
- Comparison: We compare the frequency maps.
Summary
Determining if two strings are anagrams can be achieved through various methods across different programming languages. Sorting offers a straightforward approach, while using dictionaries (or hash maps) provides an efficient solution with linear time complexity. Each method has its strengths, and understanding these can help you choose the most suitable approach for your specific needs.
Discover more from lounge coder
Subscribe to get the latest posts sent to your email.
