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();
// 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++)
{
var tmp = charArray[index];
// Leave blank, need to fill the detail of BFS search
// backtracking
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)
{
/*
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.
*/
var depth = LadderLength("hit", "cog", new string[] { "hot", "dot", "dog", "lot", "log", "cog" }.ToList());
}
/// <summary>
/// code review on July 28, 2022
/// </summary>
/// <param name="beginWord"></param>
/// <param name="endWord"></param>
/// <param name="wordDict"></param>
/// <returns></returns>
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);
// 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();
var charArray = current.ToCharArray();
// 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++)
{
var tmp = charArray[index];
//var neighbor = stringReplaceAt(current, index, c); // C# string is immutable
charArray[index] = c;
// find endWord
var next = new string(charArray);
if (next.CompareTo(endWord) == 0)
{
return depth;
}
if (dict.Contains(next))
{
queue.Enqueue(next);
dict.Remove(next);
}
// backtracking
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);
// use two queue to track the change and length in the same pace
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)) { // only considers the remaining words.
if (anb.CompareTo(endWord) == 0 )
return length + 1;
q.Enqueue(anb);
qLen.Enqueue(length);
words.Remove(anb); // 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;
}
}
No comments:
Post a Comment