Leetcode discuss: 127. Word Ladder

June 7, 2022

Here is the link. 

BFS - C# - Backtracking - Tips

Dec. 7, 2020
Introduction
Based on the comment from Google | Onsite | Find Most Similar Path In Graph, I had chance to review this algorithm and practice second time.

BFS algorithm
I like to take down a few notes in the following:

1. beginWord may not be in the dictionary;
2. BFS algorithm - avoid deadloop, mark visited for each word is important, here is to remove word from HashSet.
3. Time complexity: O(M * M * N), M is length of word, N is length of dictionary.
4. For each char in the word, replace it using 'a' to 'z', at most 26 choices. So total choice is 26 * M.
5. C# string.ToCharArray() is easy to back track.
6. put depth++; statement before for loop since it is easy to make mistake to put in wrong places with more than one '}'.

public class Solution {
    public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
        if (beginWord == null || endWord == null || wordList == null || wordList.Count == 0)
            {
                return 0;
            }

            var dict = new HashSet<string>(wordList);
            if (!dict.Contains(endWord))
            {
                return 0;
            }

            var queue = new Queue<string>();

            queue.Enqueue(beginWord);

            // mark visit
            dict.Remove(beginWord);

            int depth = 0;

            while (queue.Count > 0)
            {
                int levelCount = queue.Count;
                depth++;
                // Check each adjacent string
                for (int i = 0; i < levelCount; i++)
                {
                    var current = queue.Dequeue();
                    var charArray = current.ToCharArray(); 

                    // base case
                    if(current.CompareTo(endWord) == 0)
                    {
                        return depth; 
                    }

                    // go over each char in the word first                    
                    for (int index = 0; index < charArray.Length; index++)
                    {
                        // replace by all possible neighbors
                        for (char c = 'a'; c <= 'z'; c++)
                        {
                            if (c == current[index])
                            {
                                continue;
                            }

                            var tmp = charArray[index];
                            charArray[index] = c;
                            var next = new string(charArray);                             

                            if (dict.Contains(next))
                            {
                                queue.Enqueue(next);
                                dict.Remove(next);
                            }

                            //backtracking
                            charArray[index] = tmp;
                        }
                    }                    
                }                
            }

            return 0;
    }
}

Comment