Daily LeetCode Challenge - 839. Similar String Groups

Problem From.

https://leetcode.com/problems/similar-string-groups/

오늘 문제는 strs 리스트에서 string 들이 주어질대, 그 string 들을 비슷한 그룹으로 나눠서 묶는 문제였다. 비슷한 그룹은 한 string 에서 글자 두개를 선택하여 서로 자리를 바꾸었을때, 다른 string 과 같으면 같은 그룹에 있다고 한다.

string 이 비슷한지 알아보는 가장 쉬운 방법은, 문제의 제한사항에서 모든 string 은 anagram 으로 되어있다고 하였으니, 세자리 이상 각각의 자리에 다른 글자가 나오면 그 string 은 비슷한 string 이 될 수 없다. 여기에 union find 알고리즘을 이용하여, 각각의 string 이 비슷한지 찾음과 동시에, groups 리스트에 비슷한 string 을 하나의 부모에 연결하여 같은 그룹에 묶어줄 수 있도록 만들었다.

class Solution {
    fun numSimilarGroups(a: Array<String>): Int {
        val groups = IntArray(a.size) { -1 }

        fun root(i: Int): Int {
            var x = i
            while (groups[x] != -1) {
                x = groups[x]
            }

            var y = i
            while (y != x) {
                val t = groups[y]
                groups[y] = x
                y = t
            }

            return x
        }
        
        for (i in 0 until a.size) {
            val x = root(i)
            for (j in i + 1 until a.size) {
                val y = root(j)

                if (x != y) {
                    if (similar(a[i], a[j])) {
                        groups[y] = x
                    }
                }
            }
        }

        return groups.count { it == -1 }
    }
    
    private fun similar(a: String, b: String): Boolean {
        var count = 0
        for (i in 0 until a.length) {
            if (a[i] != b[i]) {
                if (++count > 2) return false
            }
        }
        return true
    }
}