## Wednesday, January 6, 2021

### Leetcode discuss: 839. Similar String Groups

##### 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];
}
}``````