LeetCode in Ruby: 242. Valid Anagram

#leetcode #ruby #sorting

Count

def is_anagram(s, t)
  return false unless s.length == t.length

  ('a'..'z').each do |char|
    return false unless s.count(char) == t.count(char)
  end

  true
end

The two strings s and t are anagrams if they have the same number of occurrences for each character. Even its time complexity is O(n^2), it’s faster than the latter two approaches.

Time complexity: O(n^2)

Extra memory: O(1)

Sort

def is_anagram(s, t)
  return false unless s.length == t.length

  s_ary = s.split('').sort
  t_ary = t.split('').sort

  (0...s.length).each do |index|
    return false if s_ary[index] != t_ary[index]
  end

  return true
end

We convert the strings s and t into two arrays: s_ary and t_ary, with characters being sorted. If s and t are anagrams, then s_ary and t_ary must have the same character for each index. This is what the loop is checking.

Time complexity: O(nlgn)

Extra memory: O(n)

Sort (A Faster Variant)

def is_anagram(s, t)
  return false unless s.length == t.length

  s.bytes.sort! == t.bytes.sort!
end

This is the same as the previous one, except that we aren’t comparing characters but bytes.