Question

Formatted question description: https://leetcode.ca/all/242.html

 242	Valid Anagram

 Given two strings s and t , write a function to determine if t is an anagram of s.

 Example 1:

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

 Example 2:

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

 Note:
 You may assume the string contains only lowercase alphabets.

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

Algorithm

The core point lies in the use of hash table mapping, using an array to act as the hash table.

First judge whether the two strings have the same length, if they are not the same, return false directly.

Then count the number of occurrences of all the characters in s and store them in an array of size 26, because the input string is limited to lowercase letters in the title.

Then we will count the t string again, and return false if it does not match.

Code

Java

import java.util.Arrays;

public class Valid_Anagram {

    public static void main(String[] args) {

        Valid_Anagram out = new Valid_Anagram();
        Solution2 s = out.new Solution2();

        System.out.println(s.isAnagram("anagram!@#$%", "!@#$%nagaram"));
    }


    class Solution {
        public boolean isAnagram(String s, String t) {
            if (s.length() != t.length()) {
                return false;
            }
            char[] str1 = s.toCharArray(); // NlogN
            char[] str2 = t.toCharArray();
            Arrays.sort(str1);
            Arrays.sort(str2);

            // direct compare
            return Arrays.equals(str1, str2);
        }
    }

    public class Solution2 {
        public boolean isAnagram(String s, String t) {

            int[] count = new int[256];

            for (int i = 0; i < s.length(); i++) {
//                count[s.charAt(i) - 'a']++; // O(N)
                count[s.charAt(i) - '!']++; // O(N)
            }
            for (int i = 0; i < t.length(); i++) {
//                count[t.charAt(i) - 'a']--;

                // @note: for followup question, if use `a` then result will be -64. so use 1st unicode
                // or, use a valid map data structure, instead of int array
                count[t.charAt(i) - '!']--;
            }

            for (int i : count) {
                if (i != 0) return false;
            }

            return true;
        }
    }
}

// OJ: https://leetcode.com/problems/valid-anagram/
// Time: O(N)
// Space: O(C)
class Solution {
public:
    bool isAnagram(string s, string t) {
        int cnt[26] = {};
        for (char c : s) cnt[c - 'a']++;
        for (char c : t) cnt[c - 'a']--;
        for (int n : cnt) {
            if (n) return false;
        }
        return true;
    }
};

class Solution(object):
  def isAnagram(self, s, t):
    """
    :type s: str
    :type t: str
    :rtype: bool
    """
    if not len(s) == len(t):
      return False

    sHash = tHash = 1
    sCount = [0] * 26
    tCount = [0] * 26
    p1 = 2903
    p2 = 29947
    for i in range(0, len(s)):
      sCount[ord(s[i]) - ord('a')] += 1
      tCount[ord(t[i]) - ord('a')] += 1

    for i in range(0, 26):
      sHash = sHash * p1 + sCount[i]
      tHash = tHash * p1 + tCount[i]
      p1 *= p2
    return sHash == tHash

242 - Valid Anagram

Question

Algorithm

Code

All Problems

All Solutions