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);
}
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);
}
public static bool AreSentencesSimilarTwo(string[] sentence1, string[] sentence2, IList<IList<string>> similarPairs)
{
if(sentence1 == null || sentence2 == null || sentence1.Length != sentence2.Length)
{
return false;
}
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);
}
var length = sentence1.Length;
for (var index = 0; index < length; index++)
{
var word1 = sentence1[index];
var word2 = sentence2[index];
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;
}
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;
}
}
}
