Solution For Valid Anagram
Problem Statement:
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
Example 1:
Input: s = “anagram”, t = “nagaram”
Output: true
Example 2:
Input: s = “rat”, t = “car”
Output: false
Solution:
The approach here is to count the occurrence of each character in both the strings and compare them. If the count of the occurrences of every character in both strings is the same, then the second string is an anagram of the first string.
Algorithm:
- If the lengths of the two strings are not equal, return false as they cannot be anagrams then.
- Initialize an array of size 26 to represent the occurrences of each character in the strings using the ASCII value of each character.
- Traverse the first string, and for each character increment the array value at the corresponding index.
- Traverse the second string, and for each character decrement the array value at the corresponding index.
- Finally, traverse the character array, if for any index the value is non-zero, then the second string is not an anagram of the first string.
Code:
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
occurrences = [0] * 26
for char in s:
occurrences[ord(char) - ord('a')] += 1
for char in t:
occurrences[ord(char) - ord('a')] -= 1
for val in occurrences:
if val != 0:
return False
return True
Time Complexity: O(n) – As we traverse both the strings only once.
Space Complexity: O(1) – We are using only an array of constant size which is 26.
Step by Step Implementation For Valid Anagram
public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { return false; } int[] counter = new int[26]; for (int i = 0; i < s.length(); i++) { counter[s.charAt(i) - 'a']++; counter[t.charAt(i) - 'a']--; } for (int count : counter) { if (count != 0) { return false; } } return true; }
def isAnagram(s, t): # Sort both strings s_sorted = "".join(sorted(s)) t_sorted = "".join(sorted(t)) # Compare sorted strings return s_sorted == t_sorted
var isAnagram = function(s, t) { //if the lengths of the two input strings are not the same, they cannot be anagrams if (s.length !== t.length) { return false; } //create two objects to store the counts of each character in the input strings let sCharCounts = {}; let tCharCounts = {}; //iterate through the first string and store the counts of each character in the first object for (let i = 0; i < s.length; i++) { let currentChar = s[i]; if (sCharCounts[currentChar]) { sCharCounts[currentChar]++; } else { sCharCounts[currentChar] = 1; } } //iterate through the second string and store the counts of each character in the second object for (let i = 0; i < t.length; i++) { let currentChar = t[i]; if (tCharCounts[currentChar]) { tCharCounts[currentChar]++; } else { tCharCounts[currentChar] = 1; } } //compare the two objects - if they have the same key/value pairs, the input strings are anagrams for (let key in sCharCounts) { if (!(key in tCharCounts)) { return false; } if (tCharCounts[key] !== sCharCounts[key]) { return false; } } return true; };
class Solution { public: bool isAnagram(string s, string t) { if(s.length() != t.length()) return false; int n = s.length(); int count[26] = {0}; for(int i = 0; i < n; i++){ count[s[i]-'a']++; count[t[i]-'a']--; } for(int i = 0; i < 26; i++){ if(count[i]) return false; } return true; } };
public bool IsAnagram(string s, string t) { // If the two strings are not of equal length, // then they cannot be anagrams if (s.Length != t.Length) { return false; } // Sort both the strings Array.Sort(s.ToCharArray()); Array.Sort(t.ToCharArray()); // Compare the sorted strings for (int i = 0; i < s.Length; i++) { if (s[i] != t[i]) { return false; } } return true; }