Leetcode discuss: 737. Sentence Similarity II

July 10, 2021

Here is the link. 

C# | Graph using adjacent list | DFS | Warmup

July 10, 2021
Introduction
It is my warmup practice to prepare for a phone screen on July 12, 2021. I like to work on a few algorithms, graph, tree, dynamic programming and go over all hard level algorithms I studied to prepare for Google onsite in Dec. 2020. I just started to work on algorithm on my discussion post here called 600 beyond.

Graph | Undirected graph | use Hashmap | Common exception
I wrote C# code and then ran into exception. I did not think carefully, instead I copied the test case and then ran it in visual studio. The error is clear inside visual studio. The word may not in graph at all, null pointer exception.

The following code passes online judge.

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

namespace _737_sentence_similarity
{
    class Program
    {
        static void Main(string[] args)
        {
            RunTestcase2(); 
        }

        public static void RunTestcase1()
        {
            var sentence1 = new string[] { "great", "acting", "skills" };
            var sentence2 = new string[] { "fine", "drama", "talent" };

            var pairs = new List<IList<string>>();
            pairs.Add(new string[] { "great", "good" }.ToList());
            pairs.Add(new string[] { "fine", "good" }.ToList());
            pairs.Add(new string[] { "drama", "acting" }.ToList());
            pairs.Add(new string[] { "skills", "talent" }.ToList());

            var result = AreSentencesSimilarTwo(sentence1, sentence2, pairs); 
        }

        /// failed test case - 14/119 - investigate the issue 
        public static void RunTestcase2()
        {            
            var sentence1 = new string[]{"a","very","delicious","meal"};
            var sentence2 = new string[]{"one","really","good","dinner"};

            var pairs = new List<IList<string>>();
            pairs.Add(new string[]{"great","good"}.ToList());
            pairs.Add(new string[]{"extraordinary","good"}.ToList());
            pairs.Add(new string[]{"well","good"}.ToList());
            pairs.Add(new string[]{"wonderful","good"}.ToList());
            pairs.Add(new string[]{"excellent","good"}.ToList());            

            var items = new string[][]{
            new string[]{"fine","good"},new string[]{"nice","good"},new string[]{"any","one"},new string[]{"some","one"},new string[]{"unique","one"},new string[]{"the","one"},
            new string[]{"an","one"},new string[]{"single","one"},new string[]{"a","one"},new string[]{"truck","car"},new string[]{"wagon","car"},new string[]{"automobile","car"},
            new string[]{"auto","car"},new string[]{"vehicle","car"},new string[]{"entertain","have"},new string[]{"drink","have"},new string[]{"eat","have"},
            new string[]{"take","have"},new string[]{"fruits","meal"},new string[]{"brunch","meal"},new string[]{"breakfast","meal"},new string[]{"food","meal"},
            new string[]{"dinner","meal"},new string[]{"super","meal"},new string[]{"lunch","meal"},new string[]{"possess","own"},new string[]{"keep","own"},
            new string[]{"have","own"},new string[]{"extremely","very"},new string[]{"actually","very"},new string[]{"really","very"},new string[]{"super","very"}};

            foreach (var item in items)
            {
                pairs.Add(item.ToList());
            }

            AreSentencesSimilarTwo(sentence1, sentence2, pairs);             
        }

        /// <summary>
        /// Graph - how to build an undirected graph using adjacent list. 
        /// How to search a graph using BFS/ DFS and avoid deadloop - mark visit
        /// Transitive
        /// ["great", "good"], ["fine","good"], so "great","good" and "fine" are all connected. 
        /// Brute force solution
        /// Search graph for connected words, check if there is a match
        /// </summary>
        /// <param name="sentence1"></param>
        /// <param name="sentence2"></param>
        /// <param name="similarPairs"></param>
        /// <returns></returns>
        public static bool AreSentencesSimilarTwo(string[] sentence1, string[] sentence2, IList<IList<string>> similarPairs)
        {
            if(sentence1 == null || sentence2 ==  null || sentence1.Length != sentence2.Length)
            {
                return false; 
            }

            // build a graph
            var graph = new Dictionary<string, List<string>>(); 
            foreach(var pair in similarPairs)
            {
                if (pair.Count() < 2)
                {
                    continue; 
                }

                var node1 = pair[0];
                var node2 = pair[1]; 
                if(!graph.ContainsKey(node1))
                {
                    graph.Add(node1, new List<string>());
                }
                
                if(!graph.ContainsKey(node2))
                {
                    graph.Add(node2, new List<string>());
                }

                graph[node1].Add(node2);
                graph[node2].Add(node1);
            }

            // search the graph
            var length = sentence1.Length;
            for (var index = 0; index < length; index++)
            {
                var word1 = sentence1[index];
                var word2 = sentence2[index];

                // DFS - search word1 connected graph
                var seenWords = new HashSet<string>();
                var stack = new Stack<string>();
                stack.Push(word1);
                var found = false; 

                while(stack.Count > 0)
                {
                    var visit = stack.Pop();
                    seenWords.Add(visit);

                    if (visit.CompareTo(word2) == 0)
                    {
                        found = true;
                        break; 
                    }

                    // caught by online judge - failed test case - 14/119
                    if(!graph.ContainsKey(visit))
                    {
                        continue; 
                    }

                    foreach(var word in graph[visit])
                    {
                        if (seenWords.Contains(word))
                        {
                            continue; 
                        }

                        stack.Push(word);
                    }
                }

                if(!found)
                {
                    return false; 
                }            
            }

            return true; 
        }
    }
}