C# BFS Solution


  • 0
    C

    For each char in start we generate all the possible mutations and we place them in a queue. One by one we process the queue to see if any of this mutations is

    • equal to end
    • already visited
    • in the world bank

    We need to keep track on which level of the BFS tree we are to make sure we increase the mutation results count accordingly.

    BFS will guaranteed the shortest possible mutation to end if possible.

    Possible optimization:

    • use 2 bits instead of CHAR to encode the genes
    public class Solution {
        
        private char[] genes = new char[] {'A','C','G','T' }; 
        
        public int MinMutation(string start, string end, string[] bank) {
            var visited = new HashSet<string>();
            var q = new Queue<string>();
            var set = new HashSet<string>();
            foreach(var s in bank) set.Add(s);
            
            if(!set.Contains(end)) return -1;
            
            int mutation = -1;
            q.Enqueue(start);
            
            while(q.Count > 0) {
                int count = q.Count;
                mutation++;
                
                // we need to check each level of the BFS
                for(int i = 0; i < count; i++) {
                    string s = q.Dequeue();
                    if(s == end) {
                        // done
                        return mutation;
                    }
                    
                    foreach(var mut in GetStringMutations(s)) {
                        if(set.Contains(mut) && !visited.Contains(mut)) {
                            q.Enqueue(mut);    
                        }
                    }
                }
            }
            
            return -1;
        }
        
        public IList<string> GetStringMutations(string gene) {
            IList<string> res = new List<string>();
            
            for(int i = 0; i < gene.Length; i++) {
                foreach(var c in genes) {
                    if(gene[i] != c) {
                        var newGene = new StringBuilder(gene);
                        newGene[i] = c;
                        res.Add(newGene.ToString());
                    }
                }
            }
            
            return res;
        }
    }```

Log in to reply
 

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