Nov. 10, 2020
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:
- Time complexity is O(N x M), N is the length of words, M is number of pairs.
- DFS - not using recursive function, using a stack, and avoid deadloop, use visited HashSet<string>
- 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
- Compared to union find algorithm, DFS is not optimal compared to time complexity.
- Be a good thinker! Read more solutions shared by Leetcode.com solution tab first.
Here is the gist.