Leetcode discuss: 1258. Synonymous Sentences

 Here is my discuss post. 

C# | mock interview | Extra one hour | Union Find | DFS | Copy one line

Feb. 19, 2021
Introduction
It is such great learning experience to manage my practice on Leetcode premium Amazon online assessment. I came cross the algorithm, and I had over 30 minutes in mock interview to work on the algorithm first, and then I spent another 40+ minutes to finish code. I needed to debug the code to fix a Union Find algorithm's bug, and then another issue related to StringComparison.Ordinal, 20+ minutes research.

My approach
I decided to post a discussion to document my practice first. And then I had to look up C# discussion post, and then found the tip. The change is the following

list.Sort();

to

list.Sort(StringComparer.Ordinal);

The following code passes online judge.

Performance
I do think that it is so important for me to master as many as algorithms on Leetcode.com using C# first, so that I can apply my skills to my future projects at work.

Blessing
It is blessing that I do not have high paid job, so that I can keep practicing more algorithms and keep learning. I will be super star one day in algorithm and data structure. Image that I can have this strong research and problem solving skills, I can easily convert it to another area, bring a lot of financial success in my personal wealth building. Stay confident.

public class Solution {
    public IList<string> GenerateSentences(IList<IList<string>> synonyms, string text)
        {
            if (synonyms == null || text == null || text.Length == 0)
            {
                return new List<string>(); 
            }

            var rows = synonyms.Count;

            var words = new HashSet<string>();
            foreach (var item in synonyms)
            {
                foreach (var word in item)
                {
                    words.Add(word); 
                }
            }

            var list = words.ToList();
            list.Sort(StringComparer.Ordinal);
            var length = list.Count; 

            var map = new Dictionary<string, int>();
            for (int i = 0; i < list.Count; i++)
            {
                map.Add(list[i], i); 
            }

            // apply union find algorithm 
            var parents = new int[length];
            for (int i = 0; i < length; i++)
            {
                parents[i] = i; 
            }

            foreach (var item in synonyms)
            {
                var item1 = item[0];
                var item2 = item[1];

                var id1 = map[item1];
                var id2 = map[item2];

                // union find algorithm 
                parents[findParent(parents, Math.Max(id1, id2))] = findParent(parents, Math.Min(id1, id2));
            }

            // added after failed first test case
            for (int i = 0; i < length; i++)
            {
                parents[i] = findParent(parents, i);
            }

            // apply DFS algorithm 
            // replace every possible word - go through parents table 
            var replaced = new List<string>();
            var split = text.Split(' ');

            applyDFS(parents, list, map, split, 0, replaced);

            return replaced; 
        }

        /// <summary>
        /// Feb. 19, 2021
        /// </summary>
        /// <param name="parents"></param>
        /// <param name="list"></param>
        /// <param name="map"></param>
        /// <param name="split"></param>
        /// <param name="index"></param>
        /// <param name="replaced"></param>
        private static void applyDFS(int[] parents, List<string> list, Dictionary<string, int> map, string[] split, int index, List<string> replaced)
        {
            // base case
            if (index == split.Length)
            {
                replaced.Add(string.Join(" ", split));
                return; 
            }

            var current = split[index];
            var found = map.ContainsKey(current);

            if (!found)
            {
                applyDFS(parents, list, map, split, index + 1, replaced);
            }
            else
            {
                var id = map[current];
                var parent = parents[id];
                for (int i = 0; i < parents.Length; i++)
                {
                    if (parents[i] == parent)
                    {
                        var similar = list[i];
                        var copy = split[index];
                        split[index] = similar;

                        applyDFS(parents, list, map, split, index + 1, replaced);
                        split[index] = copy; // backup
                    }
                }
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="parents"></param>
        /// <param name="id"></param>
        private static int findParent(int[] parents, int id)
        {
            if(parents[id] == id)
            {
                return id; 
            }

            parents[id] = findParent(parents, parents[id]);
            return parents[id]; 
        }
}