Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class Solution
- {
- private int VisitNode(Queue<Payload> q,
- Dictionary<string, Node> nodes,
- Dictionary<string, int> visited,
- Dictionary<string, int> otherVisited)
- {
- var payload = q.Dequeue();
- foreach(var p in nodes[payload.Word].Relationship)
- {
- if (otherVisited.ContainsKey(p))
- {
- return payload.Depth + otherVisited[p];
- }
- if (!visited.ContainsKey(p))
- {
- q.Enqueue(payload.Clone(p));
- }
- visited[p] = payload.Depth + 1;
- }
- return -1;
- }
- public int LadderLength(string beginWord, string endWord, IList<string> wordList)
- {
- Dictionary<string, Node> nodes = new Dictionary<string, Node>();
- wordList.Add(beginWord);
- // Create a graph
- foreach(var current in wordList)
- {
- Node currentNode = null;
- if (!nodes.ContainsKey(current))
- {
- currentNode = new Node(current);
- nodes.Add(current, currentNode);
- } else
- {
- currentNode = nodes[current];
- }
- foreach(var candidate in wordList)
- {
- if (IsTransformable(current, candidate))
- {
- currentNode.Add(candidate);
- }
- }
- }
- if (!nodes.ContainsKey(endWord)) return 0;
- // Traverse with BFS
- Queue<Payload> sq = new Queue<Payload>();
- sq.Enqueue(new Payload
- {
- Depth = 1,
- Word = beginWord
- });
- Queue<Payload> eq = new Queue<Payload>();
- eq.Enqueue(new Payload
- {
- Depth = 1,
- Word = endWord
- });
- Dictionary<string, int> startVisited = new Dictionary<string, int>();
- Dictionary<string, int> endVisited = new Dictionary<string, int>();
- startVisited[beginWord] = 1;
- endVisited[endWord] = 1;
- while(sq.Count != 0 && eq.Count != 0)
- {
- // Start queue
- int ans = VisitNode(sq, nodes, startVisited, endVisited);
- if (ans > -1)
- {
- return ans;
- }
- // End queue
- ans = VisitNode(eq, nodes, endVisited, startVisited);
- if (ans > -1)
- {
- return ans;
- }
- }
- // Once you found the target it is the shortest depth.
- return 0;
- }
- internal static bool IsTransformable(string a, string b)
- {
- int counter = 0;
- for (int i = 0; i < a.Length; i++)
- {
- if (a[i] == b[i]) counter++;
- }
- return ((a.Length - counter) == 1);
- }
- }
- public class Payload
- {
- string _word;
- public string Word
- { get; set; }
- public int Depth { get; set; }
- public Payload Clone(string word)
- {
- var payload = new Payload();
- payload.Word = word;
- payload.Depth = this.Depth + 1;
- return payload;
- }
- }
- public class Node
- {
- private HashSet<string> _relationship = new HashSet<string>();
- public string Value { get; set; }
- public Node(string value)
- {
- Value = value;
- }
- public void Add(string relation)
- {
- _relationship.Add(relation);
- }
- public HashSet<string> Relationship => _relationship;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement