Leetcode discuss: 1258. Synonymous Sentences

 Here is the link. 

C# | DFS | Backtracking | Union find | StringComparison.Ordinal | more challenges

Feb. 19, 2021
Introduction
I have 11 years full time job using C#, but I still have not spent enough time to figure out how to make the algorithm work. The algorithm is challenge, since I put together a union find algorithm, DFS algorithm, and then I came cross this issue to deal with C# string.CompareTo(), I need to specify StringComparison.Ordinal.

Case study
C# List.Sort() algorithm applies to two strings "a", "QrbCl"; Based on ascii value, A - 65, a - 97, so it is true that "Q" < "a", but C# string.CompareTo() return -1, "a".CompareTo("QrbCl") will return -1.

Mock interview
I worked on Leetcode premium Amazon online assessment, I had 40 minutes, but I could not make it work.

Union find algorithm I had to add one more for loop after union algorithm,

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

Union find algorithm case study
["happy","joy"],["sad","sorrow"],["joy","cheerful"]

What I did is to put all distinct words into hashset, and then sort them. The list of strings are "cheerful", "happy", "joy", "sad", "sorrow". The hashmap will have
"cheerful" - 0 , "happy" - 1, "joy" - 2, "sad" - 3, "sorrow" - 4

Union find algorithm is hard to write perfectly the first time. I have practiced over 20 times on various algorithms.

Go over ["happy","joy"], so parents[2] = 1;
Go over ["sad","sorrow"], so parents[4] = 3;
Go over ["joy","cheerful"], so 2's parent's parent (1) should be 0's parent, so parents[1] = 0.

So parents array has values [0, 0, 1,3, 4], What is going on? We need to apply another round path compression, so that 2's parent is 1, which should be 1's parent 0. 1 is no longer root of tree. In other words, make sure that all parent value should be a root node's value.

And then I wrote DFS algorithm to get all combinations of synonyms.

Follow up
I will figure out how to make it work in short future. I like to study other C# submissions.

Failed test case
30 / 37 test cases passed.
Status: Wrong Answer
Submitted: 39 minutes ago
Input:
[["a","QrbCl"]]
"d QrbCl ya ya NjZQ"
Output:
["d a ya ya NjZQ","d QrbCl ya ya NjZQ"]
Expected:
["d QrbCl ya ya NjZQ","d a ya ya NjZQ"]

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace uninFindSearch
{
    class Program
    {
        /*
            synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]],
            text = "I am happy today but was sad yesterday"
        */
        static void Main(string[] args)
        {
            RunTestcase2(); 
        }

        public static void RunTestcase1()
        {
            var synonyms = new List<IList<string>>();

            synonyms.Add(new string[] { "happy", "joy" }.ToList());
            synonyms.Add(new string[] { "sad", "sorrow" }.ToList());
            synonyms.Add(new string[] { "joy", "cheerful" }.ToList());
            var text = "I am happy today but was sad yesterday";

            var result = GenerateSentences(synonyms, text);
        }

        public static void RunTestcase2()
        {
            var synonyms = new List<IList<string>>();

            synonyms.Add(new string[] { "a","QrbCl" }.ToList());
           
            var text = "d QrbCl ya ya NjZQ";

            var result = GenerateSentences(synonyms, text);
        }

        /// <summary>
        /// 34 minutes 
        /// </summary>
        /// <param name="synonyms"></param>
        /// <param name="text"></param>
        /// <returns></returns>
        public static 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); 
                }
            }

            // https://social.msdn.microsoft.com/Forums/vstudio/en-US/5dfcfff2-c963-4032-b72b-d486ef71e27c/question-about-stringcompareto?forum=csharpgeneral
            var list = words.ToList();
            
            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]; 
        }
    }
}