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.