Parition into anagrams
Given an array of strings, sort them such that the anagrams appear together.
Example
Input: elvis, silent, debitcard, lives, listen, badcredit
Output: elvis, lives, silent, listen, debitcard, badcredit
Solution
- Use a sorting technique to sort them by anagram order
- For the comparator, check if 2 strings are anagrams or not
- Naive technique is to sort both the strings and compare O(n log n)
- Faster approach is to use a hash table, track the num elements and check if they are anagrams
Code
def anagram_order(arr)
return nil if arr.nil?
sort(arr, comparator_function)
end
def comparator_function(element1, element2)
is_anagram(element1, element2)
end
# Return a hash of anagrams
def anagram_map(arr)
return nil if arr.nil?
anagrams = {}
arr.each do |str|
sorted_str = str.sort
if anagrams[sorted_str]
list = anagrams[sorted_str]
list << s
anagrams[sorted_str] = list
else
list = []
list << s
anagrams[sorted_str] = list
end
anagrams
end
def is_anagram(str1, str2)
return false if str1.size != str2.size
string_hash = {}
# Count chars in string 1
str1.each_char do |c|
if string_hash[c].nil?
string_hash[c] = 1
else
string_hash[c] += 1
end
end
# Check with chars in string 2
str2.each do |c|
if string_hash[c].nil?
return false
elsif string_hash[c] == 0
return false
else
string_hash[c] -= 1
end
end
true
end