How To Check If a String Is a Valid Anagram

How To Check If a String Is a Valid Anagram

Three C++ solutions for solving Leetcode 242. Valid Anagram. An anagram is a word formed by rearranging the letters of another word.

Problem statement

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1

Input: s = "anagram", t = "nagaram"
Output: true

Example 2

Input: s = "rat", t = "car"
Output: false

Constraints

  • 1 <= s.length, t.length <= 5 * 10^4.

  • s and t consist of lowercase English letters.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Solution 1: Rearrange both s and t into a sorted string

Code

#include <iostream>
#include <algorithm>
using namespace std;
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;
}
int main() {
    cout << isAnagram("anagram", "nagaram") << endl;
    cout << isAnagram("rat", "car") << endl;
}
Output:
1
0

Complexity

  • Runtime: O(NlogN), where N = s.length.

  • Extra space: O(1).

Solution 2: Count the appearances of each letter

Code

#include <iostream>
using namespace std;
bool isAnagram(string s, string t) {
    if (s.length() != t.length()) {
        return false;
    }
    int alphabet[26];
    for (int i = 0; i < 26; i++) {
        alphabet[i] = 0;
    }
    for (char& c : s) {
        alphabet[c - 'a']++;
    }
    for (char& c : t) {
        alphabet[c - 'a']--;
        if (alphabet[c - 'a'] < 0) {
            return false;
        }
    }
    return true;    
}
int main() {
    cout << isAnagram("anagram", "nagaram") << endl;
    cout << isAnagram("rat", "car") << endl;
}
Output:
1
0

Complexity

  • Runtime: O(N), where N = s.length.

  • Extra space: O(1).

Solution 3: If the inputs contain Unicode characters

In the solutions above, the array alphabet represents 26 letters 'a' to 'z'. You can generalize to allow it contains any character by using a map.

Code

#include <iostream>
#include <unordered_map>
using namespace std;
bool isAnagram(string s, string t) {
    if (s.length() != t.length()) {
        return false;
    }
    unordered_map<char, int> alphabet;
    for (char& c : s) {
        alphabet[c]++;
    }
    for (char& c : t) {
        alphabet[c]--;
        if (alphabet[c] < 0) {
            return false;
        }
    }
    return true;    
}
int main() {
    cout << isAnagram("anagæam", "nagaæam") << endl;
    cout << isAnagram("rat", "car") << endl;
}
Output:
1
0

Complexity

  • Runtime: O(N), where N = s.length.

  • Extra space: O(1).


Key takeaway

  • An array of 26 integers can represent the English alphabet.

  • Counting the appearances can help identify if a word is a permutation of another.

  • You can use a map to count the appearances of the letters of a word.


Thanks for reading! Get my book "10 Classic Coding Challenges" for FREE.