Leetcode discuss: 127. Word Ladder

 June 7, 2022

Here is the link. 

C# BFS practice in 2019

It is the graph problem and I like to apply breadth first search algorithm in my practice.

Here are highlights:

1. Understand how to construct a graph from startWord to endWord with distance one between each connected words, and all connected words should be in given dictionary;
2. Understand breadth first search, count the queue's size before visiting each node in the queue;
3. Mark visited node in the graph, using tip to remove word from dictionary. Also argue that it should be OK for different paths to mark visited node.
4. Work on coding style, make sure that code is readable and the result is correct.

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

namespace _127_word_ladder
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// code review on 2019 July 2
        /// </summary>
        /// <param name="beginWord"></param>
        /// <param name="endWord"></param>
        /// <param name="wordDict"></param>
        /// <returns></returns>
        public int LadderLength(string beginWord, string endWord, IList<string> wordDict)
        {
            if (beginWord == null || endWord == null || wordDict == null || wordDict.Count == 0)
            {
                return 0;
            }

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

            var queue = new Queue<string>();

            queue.Enqueue(beginWord);
            
            // mark visit
            dict.Remove(beginWord); 

            int depth = 1;

            while (queue.Count > 0)
            {
                int count = queue.Count;
                depth++; 

                // Check each adjacent string
                for (int layer = 0; layer < count; layer++) 
                {
                    var current = queue.Dequeue();

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

                            var neighbor = stringReplaceAt(current, index, c); // C# string is immutable

                            // find endWord
                            if (neighbor.CompareTo(endWord) == 0)
                            {
                                return depth;
                            }

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

            return 0;
        }

        /// <summary>
        /// write my own function
        /// </summary>
        /// <param name="s"></param>
        /// <param name="index"></param>
        /// <param name="c"></param>
        /// <returns></returns>
        private static String stringReplaceAt(String s, int index, char c)
        {
            var array = s.ToCharArray();
            array[index] = c;

            return new String(array);
        }
    }
}

user1287o587
July 16, 2020 8:43 AM
Read More
@jianminchen I have been following your answers for quite some time, It's nice to see how you improve over the time and revisit the problems and improve on top of it.
Any advise for the fellow mate on how you keep track of older problems to revisit ?
0
Hide 1 reply
Reply
Share
Report
jianminchen690
a few seconds ago
Read More
Any advise for the fellow mate on how you keep track of older problems to revisit ?
I think that it is so hard to find time to revisit problems solved before. I solved around 692 problems. My goal is to learn from the best, like votrubac - https://leetcode.com/votrubac/, so recently I chose top voted discussion posts from votrubac, and then review top voted 60 algorithms. I had chance to review some algorithms, and I did compare my performance to votrubac.
I also tried to use Leetcode -> My List, and then create a few lists to document my practice to prepare for onsite interviews. Last two year, I also paid Leetcode premium, so that I can read solutions provided by Leetcode for premium users, and also work on mock interview from Amazon, Microsoft, Google, Facebook.
I also spend time to write some discuss post to list algorithms I practice, even though it is hard for players to find the page, I try my best to get feedbacks from peers. https://leetcode.com/discuss/interview-question/1914695/30-days-to-meta-onsite-4th-facebook-onsite-system-design-daily-update-day-29
One more discuss post: https://leetcode.com/discuss/general-discussion/994399/leetcode-600-questions-beyond-strategies-and-tips
0
Reply
Share
Edit
Delete
venendroid149
December 24, 2019 7:52 AM
Read More
@jianminchen Nice solution.