Leetcode 127 - ladder length - using queue, BFS search, use Tuple class including word and ladder length.

Leetcode127_wordLadderI_p3.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode127WordLadder
{
    class Program
    {
        /*
         * Leetcode 127: Word Ladder I 
         * problem statement: 
         * https://leetcode.com/problems/word-ladder/
           Given two words (beginWord and endWord), and a dictionary's word list, 
         * find the length of shortest transformation sequence from beginWord to 
         * endWord, such that:

            Only one letter can be changed at a time
            Each intermediate word must exist in the word list
            For example,

            Given:
            beginWord = "hit"
            endWord = "cog"
            wordList = ["hot","dot","dog","lot","log"]
            As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
            return its length 5.
         */
        static void Main(string[] args)
        {
            string beginWord = "hit";
            string endWord = "cog";
            string[] arr = new string[5] { "hot", "dot", "dog", "lot", "log" };
            HashSet<string> wordList = new HashSet<string>(arr);

            int length = ladderLength(beginWord, endWord, wordList);
        }

        /*
         * All are lowercase characters
         * string is alias of System.String
         * 
         * Using Queue to do BFS search 
         * 
         * Read Tuple class in C#: 
         * https://msdn.microsoft.com/en-us/library/system.tuple(v=vs.110).aspx
         */
        public static int ladderLength(
                string beginWord,
                string endWord,
                ISet<string> wordDict
            )
        {
            if (beginWord.CompareTo(endWord) == 0) return 0;

            HashSet<string> words = new HashSet<string>();

            words = new HashSet<string>(wordDict);

            words.Add(endWord);                      

            Queue<Tuple<string, int>> queue = new Queue<Tuple<string, int>>();
            queue.Enqueue(new Tuple<string, int>(beginWord, 0));             
            
            bool found = false;
            while (queue.Count > 0 && !found)
            {
                Tuple<string, int> removed = queue.Dequeue();

                int ladderLength = removed.Item2 + 1;

                List<String> neighbors = wordNeighbor(removed.Item1);

                foreach (string s in neighbors)
                {
                    if (words.Contains(s))
                    { // only considers the remaining words.
                        if (s.CompareTo(endWord) == 0)
                            return ladderLength + 1;

                        queue.Enqueue(new Tuple<string, int>(s, ladderLength));                      

                        words.Remove(s);    // remove word from dictionary - HashSet! 
                    }
                }
            }

            return 0;
        }

        /*
         * wordNeighbor: 
         * hit - what is size of List<string> as "hit" word's neighbors
         * Go throgh each char in "hit" string, 
         * h, can be replaced by any char from 'a' to 'z', 26 in total. 
         * (any replacement of 'h') + "it"  - 26 words, 
         * same applies to 'i' and 't', 
         * Total: 26 * 3 = 78 neighbors in List<string> 
         */
        private static List<string> wordNeighbor(string word)
        {

            List<string> result = new List<string>();

            for (int i = 0; i < word.Length; i++)
            {

                char[] array = word.ToCharArray();

                for (char indexChar = 'a'; indexChar <= 'z'; indexChar++)
                {
                    array[i] = indexChar;  // replace the ith char in the array                
                    result.Add(new string(array));
                }
            }

            return result;
        }
    }
}