• API
• FAQ
• Tools
• Archive
SHARE
TWEET Untitled a guest Sep 17th, 2019 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. public class Solution
2.     {
3.
4.         private int VisitNode(Queue<Payload> q,
5.             Dictionary<string, Node> nodes,
6.             Dictionary<string, int> visited,
7.             Dictionary<string, int> otherVisited)
8.         {
9.             var payload = q.Dequeue();
10.             foreach(var p in nodes[payload.Word].Relationship)
11.             {
12.                 if (otherVisited.ContainsKey(p))
13.                 {
14.                     return payload.Depth + otherVisited[p];
15.                 }
16.                 if (!visited.ContainsKey(p))
17.                 {
19.                 }
20.                 visited[p] = payload.Depth + 1;
21.             }
22.             return -1;
23.         }
24.         public int LadderLength(string beginWord, string endWord, IList<string> wordList)
25.         {
26.             Dictionary<string, Node> nodes = new Dictionary<string, Node>();
28.             // Create a graph
29.             foreach(var current in wordList)
30.             {
31.                 Node currentNode = null;
32.                 if (!nodes.ContainsKey(current))
33.                 {
34.                     currentNode = new Node(current);
36.                 } else
37.                 {
38.                     currentNode = nodes[current];
39.                 }
40.
41.                 foreach(var candidate in wordList)
42.                 {
43.                     if (IsTransformable(current, candidate))
44.                     {
46.                     }
47.                 }
48.             }
49.
50.             if (!nodes.ContainsKey(endWord)) return 0;
51.
52.             // Traverse with BFS
55.             {
56.                 Depth = 1,
57.                 Word = beginWord
58.             });
61.             {
62.                 Depth = 1,
63.                 Word = endWord
64.             });
65.
66.             Dictionary<string, int> startVisited = new Dictionary<string, int>();
67.             Dictionary<string, int> endVisited = new Dictionary<string, int>();
68.             startVisited[beginWord] = 1;
69.             endVisited[endWord] = 1;
70.
71.             while(sq.Count != 0 && eq.Count != 0)
72.             {
73.                 // Start queue
74.                 int ans = VisitNode(sq, nodes, startVisited, endVisited);
75.                 if (ans > -1)
76.                 {
77.                     return ans;
78.                 }
79.
80.                 // End queue
81.                 ans = VisitNode(eq, nodes, endVisited, startVisited);
82.                 if (ans > -1)
83.                 {
84.                     return ans;
85.                 }
86.             }
87.             // Once you found the target it is the shortest depth.
88.             return 0;
89.         }
90.
91.         internal static bool IsTransformable(string a, string b)
92.         {
93.             int counter = 0;
94.             for (int i = 0; i < a.Length; i++)
95.             {
96.                 if (a[i] == b[i]) counter++;
97.             }
98.             return ((a.Length - counter) == 1);
99.         }
100.     }
101.
102.     public class Payload
103.     {
104.         string _word;
105.         public string Word
106.         { get; set; }
107.         public int Depth { get; set; }
108.
109.         public Payload Clone(string word)
110.         {
112.             payload.Word = word;
113.             payload.Depth = this.Depth + 1;
115.         }
116.     }
117.
118.     public class Node
119.     {
120.         private HashSet<string> _relationship = new HashSet<string>();
121.         public string Value { get; set; }
122.
123.         public Node(string value)
124.         {
125.             Value = value;
126.         }
127.
128.         public void Add(string relation)
129.         {