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.                 {
  18.                     q.Enqueue(payload.Clone(p));
  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>();
  27.             wordList.Add(beginWord);
  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);
  35.                     nodes.Add(current, currentNode);
  36.                 } else
  37.                 {
  38.                     currentNode = nodes[current];
  39.                 }
  40.  
  41.                 foreach(var candidate in wordList)
  42.                 {
  43.                     if (IsTransformable(current, candidate))
  44.                     {
  45.                         currentNode.Add(candidate);
  46.                     }
  47.                 }
  48.             }
  49.  
  50.             if (!nodes.ContainsKey(endWord)) return 0;
  51.  
  52.             // Traverse with BFS
  53.             Queue<Payload> sq = new Queue<Payload>();
  54.             sq.Enqueue(new Payload
  55.             {
  56.                 Depth = 1,
  57.                 Word = beginWord
  58.             });
  59.             Queue<Payload> eq = new Queue<Payload>();
  60.             eq.Enqueue(new Payload
  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.         {
  111.             var payload = new Payload();
  112.             payload.Word = word;
  113.             payload.Depth = this.Depth + 1;
  114.             return payload;
  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.         {
  130.             _relationship.Add(relation);
  131.         }
  132.  
  133.         public HashSet<string> Relationship => _relationship;
  134.  
  135.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top