Skip to content

LeetCode: 242-Valid Anagram Solution

Last Updated on 2023-12-16 by Clay

Problem

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 * 104
  • 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

The problem is to compare the character numbers of s and t are the same. You can also think we need them are the same string after sorting.

If you value space, you can sort the strings and compare then; The time complexity is O(n*log(n)) and space complexity is O(1).

If you value speed, you can use array or map. Use array is faster, but do not complete the "Follow up". The time complexity and space complexity is O(n).


C++ Sample Code

class Solution {
public:
    bool isAnagram(string s, string t) {
        // Base case
        if (s.size() != t.size()) {
            return false;
        }

        // Init
        unordered_map<char, int> sMap;
        unordered_map<char, int> tMap;

        // Count
        for (int i=0; i<s.size(); ++i) {
            ++sMap[s[i]];
            ++tMap[t[i]];
        }

        return sMap == tMap;
    }
};



Python Sample Code

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # Base case
        if len(s) != len(t):
            return False

        # Init
        sMap = {};
        tMap = {};

        # Count
        for i in range(len(s)):
            sMap[s[i]] = sMap.get(s[i], 0) + 1
            tMap[t[i]] = tMap.get(t[i], 0) + 1

        return sMap == tMap


But in Python case, use the built-in Counter may be the better method. You just need to return Counter(s) == Counter(t).


References


Read More

Leave a Reply