Leetcode discuss: 839. Similar String Groups

 Here is the link. 

Second practice - C# - Union Find - Union API lesson learned

Jan. 6, 2020

I wrote the working solution after the bug fix - Union API functionality. Since the code I wrote in mock interview failed on one test case, I learned the lesson. The failed practice is here.

Importance
It took me more than a hour to learn to fix the problem after the mock interview. I need to be humble and stay cautious on wrong answer to apply Union Find algorithm.

public class Solution {
    // union find algorithm    
        public int NumSimilarGroups(string[] strs)
        {
            if (strs == null || strs.Length <= 1)
                return 0;

            var length = strs.Length;
            var parents = new int[length];

            for (int i = 0; i < length; i++)
            {
                parents[i] = i;
            }            

            for (int i = 0; i < length - 1; i++)
            {
                var first = strs[i];

                for (int j = i + 1; j < length; j++)
                {
                    var second = strs[j];
                    
                    if (runSimilarCheck(first, second))
                    {
                        parents[FindParent(j, parents)] = FindParent(i, parents);
                    }                    
                }
            }

            // run again 
            for (int i = 0; i < length; i++)
            {
                parents[i] = FindParent(i, parents);
            }

            var count = 0;
            for (int i = 0; i < length; i++)
            {
                if (i == parents[i])
                {
                    count++;
                }
            }

            return count;
        }

        private static bool runSimilarCheck(string s1, string s2)
        {
            var length = s1.Length;
           
            var count = 0;

            for (int i = 0; i < length; i++)
            {
                if (s1[i] != s2[i])
                {
                    count++;                    
                }
            }            

            // since s1 and s2 are anagram, there is no need to compare chars between s1 and s2. 
            return count <= 2 ;
        }

        private static int FindParent(int start, int[] parents)
        {
            if (start != parents[start])
            {
                parents[start] = FindParent(parents[start], parents);
            }

            return parents[start];
        }
}