-
Notifications
You must be signed in to change notification settings - Fork 0
/
Solution127.cs
67 lines (53 loc) · 1.63 KB
/
Solution127.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
namespace LeetCode.Solutions;
public class Solution127
{
/// <summary>
/// 127. Word Ladder - Hard
/// <a href="https://leetcode.com/problems/word-ladder">See the problem</a>
/// </summary>
public int LadderLength(string beginWord, string endWord, IList<string> wordList)
{
var wordSet = new HashSet<string>(wordList);
if (!wordSet.Contains(endWord))
{
return 0;
}
var queue = new Queue<string>();
queue.Enqueue(beginWord);
var visited = new HashSet<string>
{
beginWord
};
var level = 1;
// BFS
while (queue.Count > 0)
{
var size = queue.Count;
for (var i = 0; i < size; i++)
{
var currentWord = queue.Dequeue();
if (currentWord == endWord)
{
return level;
}
var charArray = currentWord.ToCharArray();
for (var j = 0; j < charArray.Length; j++)
{
var originalChar = charArray[j];
for (var k = 0; k < 26; k++)
{
charArray[j] = (char)('a' + k);
var newWord = new string(charArray);
if (wordSet.Contains(newWord) && visited.Add(newWord))
{
queue.Enqueue(newWord);
}
}
charArray[j] = originalChar;
}
}
level++;
}
return 0;
}
}