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.
Time complexity: O(nlgn)
Extra memory: O(n)
Top comments (0)