C# Solution (just like Word Ladder)


  • 0
    S
    public class Solution {
        public int MinMutation(string beginWord, string endWord, string[] bank) {
            HashSet<string> wordList = new HashSet<string>(bank);
            
            Dictionary<string, int> vertexes = new Dictionary<string, int>();
            vertexes.Add(beginWord, 1);
            
            while (vertexes.Count != 0){
                Dictionary<string, int> nextCandidates = new Dictionary<string, int>();
                
                foreach(var nextWord in vertexes){
                    int foundLength;
                    GetAllOneEditDistanceWords(wordList, nextWord.Key, nextWord.Value, nextCandidates, endWord, out foundLength);
                    if (foundLength != 0){
                        return foundLength - 1;
                    }
                }
                
                vertexes = nextCandidates;
            }
            
            return -1;
        }
        
        private void GetAllOneEditDistanceWords(ISet<string> wordList, string givenWord, int pathLength, Dictionary<string, int> nextCandidates, string endWord, out int foundLength){
            foundLength = 0;
            List<string> toBeRemoved = new List<string>();
            
            foreach(var word in wordList){
                if (IsOneEditDistance(word, givenWord)){
                    toBeRemoved.Add(word);
                    if (!nextCandidates.ContainsKey(word)){
                        nextCandidates.Add(word, pathLength + 1);
                    }else{
                        if (nextCandidates[word] > (pathLength + 1)){
                            nextCandidates[word] = pathLength + 1;
                        }
                    }
                    
                    if (word == endWord){
                        foundLength = nextCandidates[word];
                        return;
                    }
                }
            }
            
            foreach(var word in toBeRemoved){
                wordList.Remove(word);
            }
        }
        
        private bool IsOneEditDistance(string word1, string word2){
            int differences = 0;
            for (int i = 0; i < word1.Length; i++){
                if (word1[i] != word2[i]){
                    differences++;
                    if (differences > 1){
                        return false;
                    }
                }
            }
            
            return (differences == 1);
        }
    }
    

Log in to reply
 

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