0839-similar-string-groups.rb

# frozen_string_literal: true

# 839. Similar String Groups
# https://leetcode.com/problems/similar-string-groups
# Hard

=begin
Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y. Also two strings X and Y are similar if they are equal.

For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".

Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}. Notice that "tars" and "arts" are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list strs of strings where every string in strs is an anagram of every other string in strs. How many groups are there?

Example 1:
Input: strs = ["tars","rats","arts","star"]
Output: 2

Example 2:
Input: strs = ["omv","ovm"]
Output: 1

Constraints:
1 <= strs.length <= 300
1 <= strs[i].length <= 300
strs[i] consists of lowercase letters only.
All words in strs have the same length and are anagrams of each other.
=end

# @param {String[]} strs
# @return {Integer}
defnum_similar_groups(strs)
strs.map!do |str|
str.split("").map(&:ord)
end

@connected=strs.each_with_object({}){ |str,connected| connected[str]=[]}

max_index=strs.size.pred
strs.each_with_indexdo |str1,index1|
index1.next.uptomax_indexdo |index2|
compare(str1,strs[index2])
end
end

count_groups
end

defcompare(str1,str2)
counter=0

str1.each_with_indexdo |char1,char_index|
ifchar1 != str2[char_index]
counter += 1

breakifcounter > 2
end
end

ifcounter == 2
@connected[str1] << str2
@connected[str2] << str1
end
end

defcount_groups
counter=0

until@connected.empty?
counter += 1
connected_strs=[@connected.keys.first]

untilconnected_strs.empty?
connected_strs.map!{ |str| @connected.delete(str)}
connected_strs.compact!
connected_strs.flatten!(1)
end
end

counter
end

# **************** #
# TEST #
# **************** #

require"test/unit"
classTest_num_similar_groups < Test::Unit::TestCase
deftest_
assert_equal2,num_similar_groups(["tars","rats","arts","star"])
assert_equal1,num_similar_groups(["omv","ovm"])
end
end