Anagram Checker

excerpt: This covers the building block, array as frequency counter. tags: array-frequency-counter

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

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?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def is_anagram(s, t)
  if s.size != t.size
    return false
  end
  
  array = Array.new(26, 0) 
  
  s.chars.each do |c|
    array[c.ord - 'a'.ord] += 1
  end
  
  t.chars.each do |c|
    array[c.ord - 'a'.ord] -= 1
  end
  
  array.all? {|x| x == 0}
end

Likely mistake: Not checking if all the elements are 0 will lead to failure for edge cases. We can terminate the algorithm as soon as we find a mismatch in the strings.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def anagram?(a, b)
  return false if a.length != b.length

  ascii_a = 'a'.ord
  array = Array.new(25, 0)

  a.chars.each do |c|
    array[c.ord - ascii_a] += 1 
  end
  
  b.chars.each do |c|
    array[c.ord - ascii_a] -= 1 

    if array[c.ord - ascii_a] < 0
      return false
    end
  end
  
  return true
end

Building Block

Array as Frequency Counter