Check if two Strings are Anagrams of each other
Program for checking if two strings are Anagram of each other – Is Anagram?
Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.
An anagram is a word or phrase that can be rearranged to form another word or phrase by using all the original letters exactly once. For example, “listen” and “silent” are anagrams because they have the same letters, even though they are arranged differently.
Problem Description
You are given two lowercase English strings, s and t. Your goal is to determine if s and t are anagrams of each other. This means they should contain the exact same letters, each appearing the same number of times, but they don’t have to be in the same order.
Example 1
Input: s = "racecar", t = "carrace"
Output: true
Output: true
Example 2
Input: s = "jar", t = "jam"
Output: false
Output: false
Note – s and t consist of lowercase English letters.
Program for checking if two strings are Anagram of each other - Is Anagram Solution
Recommendation – To check if two strings are anagrams, ensure they have the same length and identical character counts; if both conditions are met, they are anagrams.
There are mainly 2 approach to solve this problem –
- Sorting Method
- Hash Table Method
- Non-Optimal method
- Optimal method
1. Sorting Method
This method sort both strings alphabetically and check if they match. If they are identical after sorting, the strings are anagrams. This method is straightforward but may be slower for long strings.
- Time complexity: O(nlogn)
- Space complexity: O(1) or O(n) depending on the sorting algorithm.
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
};
Java
public class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] sSort = s.toCharArray();
char[] tSort = t.toCharArray();
Arrays.sort(sSort);
Arrays.sort(tSort);
return Arrays.equals(sSort, tSort);
}
}
Python
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
return sorted(s) == sorted(t)
JavaScript
class Solution {
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
isAnagram(s, t) {
if (s.length !== t.length) {
return false;
}
let sSort = s.split("").sort().join();
let tSort = t.split("").sort().join();
return sSort == tSort
}
}
2. Hash Table Method
This method Count the occurrences of each character in both strings using a hash table (or dictionary). Then, compare these counts. If they’re the same, the strings are anagrams. This approach is faster and more efficient, especially for large strings.
- Time complexity: O(n)
- Space complexity: O(1)
Code(Non-Optimal)
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
unordered_map<char, int> countS;
unordered_map<char, int> countT;
for (int i = 0; i < s.length(); i++) {
countS[s[i]]++;
countT[t[i]]++;
}
return countS == countT;
}
};
Java
public class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
HashMap countS = new HashMap<>();
HashMap countT = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
countS.put(s.charAt(i), countS.getOrDefault(s.charAt(i), 0) + 1);
countT.put(t.charAt(i), countT.getOrDefault(t.charAt(i), 0) + 1);
}
return countS.equals(countT);
}
}
Python
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
countS, countT = {}, {}
for i in range(len(s)):
countS[s[i]] = 1 + countS.get(s[i], 0)
countT[t[i]] = 1 + countT.get(t[i], 0)
return countS == countT
JavaScript
class Solution {
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
isAnagram(s, t) {
if (s.length !== t.length) {
return false;
}
const countS = {};
const countT = {};
for (let i = 0; i < s.length; i++) {
countS[s[i]] = (countS[s[i]] || 0) + 1;
countT[t[i]] = (countT[t[i]] || 0) + 1;
}
for (const key in countS) {
if (countS[key] !== countT[key]) {
return false;
}
}
return true;
}
}
Code(Optimal)
- Time complexity: O(n)
- Space complexity: O(1)
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
vector count(26, 0);
for (int i = 0; i < s.length(); i++) {
count[s[i] - 'a']++;
count[t[i] - 'a']--;
}
for (int val : count) {
if (val != 0) {
return false;
}
}
return true;
}
};
Java
public class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
count[t.charAt(i) - 'a']--;
}
for (int val : count) {
if (val != 0) {
return false;
}
}
return true;
}
}
Python
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
count = [0] * 26
for i in range(len(s)):
count[ord(s[i]) - ord('a')] += 1
count[ord(t[i]) - ord('a')] -= 1
for val in count:
if val != 0:
return False
return True
JavaScript
class Solution {
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
isAnagram(s, t) {
if (s.length !== t.length) {
return false;
}
const count = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
count[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
count[t.charCodeAt(i) - 'a'.charCodeAt(0)]--;
}
return count.every(val => val === 0);
}
}
