Leetcode discuss: 127. Word Ladder

Sept. 22, 2021

Here is the link.

C# | BFS | Deadloop - TLE concern | Warmup before onsite

Sept. 23, 2021
Introduction
It is challenge for me to adjust myself to bring up best performance for my onsite interview. I chose to practice Leetcode algorithms contains "word".

BFS algorithm | deadloop - avoid loop in search | backtracking is not necessary | Two loops - All chars from 'a' to 'z'

I tried a few times in order to make the code pass online judge. Avoid loop in BFS is a must. It is challenge to make it correct to count depth of words, startWord = "cat", endWord = "cat", word dictionary is ["cat"], the result should be 2. I will look into the issue later.

The following code passes online judge.

public class Solution {
    public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
       if(beginWord == null || beginWord.Length == 0 || wordList == null || wordList.Count == 0) 
           return 0; 
        
       var hashSet = new HashSet<string>(wordList); 
        if(!hashSet.Contains(endWord))
            return 0;
        
        // apply BFS search
        var queue = new Queue<string>();
        queue.Enqueue(beginWord);
        var depth = 1; 
        while(queue.Count > 0)
        {
            depth++;
            
            var count = queue.Count;
            for(int i = 0 ; i < count; i++)
            {
                var visit = queue.Dequeue(); 
                
                for(int j = 0; j < visit.Length; j++)
                {
                    var replaced = visit.ToCharArray();
                    for(int k = 0; k < 26; k++)
                    {                        
                        replaced[j] = (char) ('a' + k);
                        var search = new string(replaced);
                        
                        if(!hashSet.Contains(search) || search.CompareTo(visit) == 0)
                        {                            
                            continue;                        
                        }            
                        
                        if(search.CompareTo(endWord) == 0)
                            return depth;
                        
                        hashSet.Remove(search); // avoid deadloop - tested! It is a must!
                        
                        queue.Enqueue(search);                                                   
                    }
                }
            }                      
        }
        
        return 0; 
    }
}