C# BFS - Shorted Path


  • 0
    J
    public class Solution
    {   
        public int OpenLock(string[] deadends, string target)
        {
            Dictionary<string, int> visited = new Dictionary<string, int>();
            foreach (string s in deadends)
            {
                if (!visited.ContainsKey(s))
                {
                    visited.Add(s, int.MaxValue);
                }
            }
            if (visited.ContainsKey("0000") || visited.ContainsKey(target))
            {
                return -1;
            }
            
            Queue<string> queue = new Queue<string>();
            queue.Enqueue("0000");
            visited.Add("0000", 0);
            
            while (queue.Any())
            {
                string current = queue.Dequeue();
                int len = visited[current];
                if (current.Equals(target))
                {
                    return len;
                }
                
                List<string> nexts = GetNexts(current);
                foreach (string next in nexts)
                {
                    if (!visited.ContainsKey(next))
                    {
                        queue.Enqueue(next);
                        visited.Add(next, len + 1);
                    }
                }
            }
            return -1;
        }
        
        private List<string> GetNexts(string s)
        {
            List<string> result = new List<string>();
            StringBuilder sb = new StringBuilder(s);
            for (int i = 0; i < s.Length; i++)
            {
                char c = s[i];
                char a = c == '9' ? '0' : (char)(c + 1);
                sb[i] = a;
                result.Add(sb.ToString());
                char b = c == '0' ? '9' : (char)(c - 1);
                sb[i] = b;
                result.Add(sb.ToString());
                sb[i] = c;
            }
            return result;
        }
    }
    

  • 0
    J

    @jaysleetcode Good one!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.