Leetcode discuss: 737. Sentence Similarity II

 Nov. 10, 2020

Introduction

It is important for me to learn a solution shared by Leetcode.com. It is surprising to learn so many things through DFS approach. 

Highlights of DFS solution:

1. Time complexity is O(N x M), N is the length of words, M is number of pairs.
2. DFS - not using recursive function, using a stack, and avoid deadloop, use visited HashSet<string>
3. First using C# hashMap Dictionary<string, List<string>> to build a graph first, go over all pairs and then record undirected graph, A -> B and also B->A
4. Compared to union find algorithm, DFS is not optimal compared to time complexity. 
5. Be a good thinker! Read more solutions shared by Leetcode.com solution tab first.  

Here is the gist. 

	public class Solution {
	/// <summary>
	/// Nov. 19, 2020
	/// study code
	/// https://leetcode.com/problems/sentence-similarity-ii/solution/
	/// Time Complexity: O(NP), where N is the maximum length of words1 and words2,
	/// and P is the length of pairs. Each of N searches could search the entire graph.
	/// </summary>
	/// <param name="words1"></param>
	/// <param name="words2"></param>
	/// <param name="pairs"></param>
	/// <returns></returns>
	public bool AreSentencesSimilarTwo(string[] words1, string[] words2, IList<IList<string>> pairs) {
	var length1 = words1.Length;
	var length2 = words2.Length;
	if (length1 != length2)
	{
	return false;
	}
	var graph = new Dictionary<string, List<string>>();
	foreach (var pair in pairs)
	{
	var first = pair[0];
	var second = pair[1];
	foreach (var p in pair)
	{
	if (!graph.ContainsKey(p))
	{
	graph.Add(p, new List<string>());
	}
	}
	graph[first].Add(second);
	graph[second].Add(first);
	}
	for (int i = 0; i < length1; ++i)
	{
	var w1 = words1[i];
	var w2 = words2[i];
	// think carefully how to use stack to apply DFS
	// need some time to figure out ...
	// instead of using recursive function, using a stack
	var stack = new Stack<string>();
	var seen = new HashSet<string>();
	stack.Push(w1);
	seen.Add(w1);
	var found = false;
	while (stack.Count > 0)
	{
	var word = stack.Pop();
	if (word.CompareTo(w2) == 0)
	{
	found = true;
	break; // while loop
	}
	if (graph.ContainsKey(word))
	{
	foreach (var neighbor in graph[word])
	{
	if (!seen.Contains(neighbor))
	{
	stack.Push(neighbor);
	seen.Add(neighbor);
	}
	}
	}
	}
	if (!found)
	{
	return false;
	}
	}
	return true;
	}
	}

view raw Leetcode737SentenceSimilarity.cs hosted with ❤ by GitHub