C# Solution beats 100%


  • 0
    K

    The biggest optimization is creating a group array, which allows us to quickly decide the neighbors for each node, without having to go through every one of the 4 letters, per index in the genetic string.

    public class Solution {
        public int MinMutation(string start, string end, string[] bank) {
            Dictionary<string, HashSet<string>> groups = new  Dictionary<string, HashSet<string>>();
            
            for (int i = 0; i < 8; i++) {
                foreach (string word in bank) {
                    string key = this.GetKeyForGroupAtIndex(i, word);
                    this.AddGroup(key, word, groups);
                }
            }
            
            Queue<int> dq = new Queue<int>();
            Queue<string> q = new Queue<string>();
            HashSet<string> visited = new HashSet<string>();
            q.Enqueue(start);
            dq.Enqueue(0);
            
            while (q.Count > 0) {
                string node = q.Dequeue();
                int depth = dq.Dequeue();
                
                if (node == end) {
                    return depth;
                }
                
                for (int i = 0; i < 8; i++) {
                    string key = this.GetKeyForGroupAtIndex(i, node);
                    if (!groups.ContainsKey(key)) {
                        continue;
                    }
                    
                    foreach (string neighbor in groups[key]) {
                        if (visited.Contains(neighbor)) {
                            continue;
                        }
                        
                        visited.Add(neighbor);
                        q.Enqueue(neighbor);
                        dq.Enqueue(depth + 1);
                    }
                }
            }
            
            return -1;
        }
        
        private string GetKeyForGroupAtIndex(int index, string word) {
            return word.Substring(0, index) + "_" + word.Substring(index + 1);
        }
        
        private void AddGroup(string key, string word, Dictionary<string, HashSet<string>> groups) {
            if (!groups.ContainsKey(key)) {
                groups[key] = new HashSet<string>();
            }
            
            groups[key].Add(word);
        }
    

    }


Log in to reply
 

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