July 28, 2022
Here is the link.
C# | Quick learner | BFS algorithm | Two solutions
July 22, 2022
Introduction
I like to share my two practices, one is in 2022, and the other one is in 2016. I like to show how I work on feedback and then improve my writing skills.
Solution 1 | BFS | C# String.ToCharArray | Backtracking
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
The idea is simple. For example, given example 1, beginWord = "hit", and start to work on each char in given word "hit", and go through all possible 26 chars to replace at given position. It is called BFS. To avoid deadloop, it is important to mark the visited word or remove visted word instead.
I choose to use C# string.ToCharArray(), and then apply backtracking inside double for loops.
var charArray = current.ToCharArray();
for (int index = 0; index < current.Length; index++)
{
for (char c = 'a'; c <= 'z'; c++)
{
var tmp = charArray[index];
charArray[index] = tmp;
}
}
Time complexity:
Given startWord's length N, 26 * N words will be searched to be a replacement for next word, and the maximum length of search should be less than length of dictionary M, so that time complexity O(26 * N * M) = O(NM).
Each replacement will take O(1) time to look up dictionary, and then comparison to the destination word take O(N) time, every char should be compared until last match.
So overall time complexity is O(NNM).
Space complexity
- Hashset is used to store all words in dictionary to get O(1) time to look up.
- Queue is used to store all replaced words with one char replacement. So maximum size of Queue should be O(M), M is total count of words in the dictionary.
So overall space complexity is O(M).
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)
{
var depth = LadderLength("hit", "cog", new string[] { "hot", "dot", "dog", "lot", "log", "cog" }.ToList());
}
public static 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);
dict.Remove(beginWord);
int depth = 1;
while (queue.Count > 0)
{
int count = queue.Count;
depth++;
for (int layer = 0; layer < count; layer++)
{
var current = queue.Dequeue();
var charArray = current.ToCharArray();
for (int index = 0; index < current.Length; index++)
{
for (char c = 'a'; c <= 'z'; c++)
{
var tmp = charArray[index];
charArray[index] = c;
var next = new string(charArray);
if (next.CompareTo(endWord) == 0)
{
return depth;
}
if (dict.Contains(next))
{
queue.Enqueue(next);
dict.Remove(next);
}
charArray[index] = tmp;
}
}
}
}
return 0;
}
}
}
Solution 2 | My practice in 2016
I also like to document my practice in 2016, and how I learn from my own experience.
Biggest lessons:
- I should work on Leetcode from 2010 to 2016 while I work on full time job in Vancouver, Canada.
- I learn much better from 2016 to 2022 since I work on Leetcode algorithm practice. I solved 704 algorithms, and also I write discuss post for most of those solved algorithms.
- How many problems I have based on my review of 2016 practice of this hard level algorithm - word ladder? I like to write down in the following.
Problems I have based on submission of the following C# code:
- Work on C# programming - understand the basics of C# programming language - using var to shorten the declaration of variable.
- Use data type like array, instead of declaration of two queues - q and qLen
- Perform time complexity analysis - it is not space efficient to store all neighbors in one C# List; all those strings are close to each other, no need to store them. Space efficiency is a big concern to design a solution.
I like to work on my writing skills as well. So I write a simple post to share my progress.
C# BFS practice back I in June 2016
It is so interesting and great experience to review my own code written in June 2016. I like the comment written above the function, but I did see a lot of places I should have learned early from 2010 to 2015 working full time using C#.
Here are highlights of solution:
- Understand using breadth first search, construct a graph based on each word with other word in dictionary with distance one;
- Work on graph, take BFS search approach.
- To avoid dead loop, mark visit of node in graph; Just simply remove the word from dictionary to mark visited.
- wordNeighbor is a function to check all possible neighbors. Go over each char in a word, replace it using 'a' to 'z' all possible 26 characters.
- Work on a test case, "hit" word and what are all neighbors of "hit". 'h' can be replaced by a char from 'a' to 'z'; and then go to next char 'i', apply same logic; apply to last char 't'.
public class Solution {
public 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<string> q = new Queue<string>();
Queue<int> qLen = new Queue<int>();
q.Enqueue(beginWord);
qLen.Enqueue(0);
int length = 1;
bool found = false;
while (q.Count > 0 && !found) {
String removed = q.Dequeue();
length = qLen.Dequeue() + 1;
List<String> neighbors = wordNeighbor(removed);
foreach (string anb in neighbors) {
if (words.Contains(anb)) {
if (anb.CompareTo(endWord) == 0 )
return length + 1;
q.Enqueue(anb);
qLen.Enqueue(length);
words.Remove(anb);
}
}
}
return 0;
}
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;
result.Add(new string(array));
}
}
return result;
}
}
