Rather long C# solution BFS


  • 0
    public class Solution {
        Dictionary<string, HashSet<string>> prevWord;
        List<IList<string>> ans;
        
        public IList<IList<string>> FindLadders(string beginWord, string endWord, IList<string> wordList)
        {
            HashSet<string> dictionary = new HashSet<string>();
            foreach (var w in wordList)
            {
                dictionary.Add(w);
            }
    
            prevWord = new Dictionary<string, HashSet<string>>();
            ans = new List<IList<string>>();
    
            HashSet<string> used = new HashSet<string>();
            Queue<string> q = new Queue<string>();
            q.Enqueue(beginWord);
    
            prevWord[beginWord] = new HashSet<string>();
            used.Add(beginWord);
            int level = 1;
            int ansLevel = 0;
            while (q.Any())
            {
                if (ansLevel >= level)
                {
                    break;
                }
    
                int count = q.Count();
                HashSet<string> nextLevelWords = new HashSet<string>();
    
                for (int i = 0; i < count; i++)
                {
                    string curWord = q.Dequeue();
                    List<string> nextWords = GetTransformations(dictionary, curWord);
                    foreach (var nw in nextWords)
                    {
                        if (nw == endWord || !used.Contains(nw))
                        {
                            if (!prevWord.ContainsKey(nw))
                            {
                                prevWord[nw] = new HashSet<string>();
                            }
    
                            prevWord[nw].Add(curWord);
    
                            if (nw == endWord)
                            {
                                ansLevel = level + 1;
                                continue;
                            }
                            else
                            {
                                nextLevelWords.Add(nw);
                            }
                        }
                    }
                }
    
                foreach (var nw in nextLevelWords)
                {
                    q.Enqueue(nw);
                    used.Add(nw);
                }
    
                level++;
            }
    
            if (prevWord.ContainsKey(endWord))
            {
                CollectAnswer(endWord, new Stack<string>());
            }
    
    
            return ans;
        }
    
        private void CollectAnswer(string curWord, Stack<string> path)
        {
            if (curWord == null)
            {
                return;
            }
    
            path.Push(curWord);
            if (prevWord.ContainsKey(curWord))
            {
                if (!prevWord[curWord].Any())
                {
                    var revPath = new List<string>(path.ToArray());
                    ans.Add(revPath);
                }
                else
                {
                    foreach (var prev in prevWord[curWord])
                    {
                        CollectAnswer(prev, path);
                    }
                }
            }
    
            path.Pop();
        }
    
        private List<string> GetTransformations(HashSet<string> dictionary, string curWord)
        {
            List<string> words = new List<string>();
            char[] wordArray = curWord.ToCharArray();
            for (int i = 0; i < wordArray.Length; i++)
            {
                char mem = wordArray[i];
                for (int ci = 0; ci < 26; ci++)
                {
                    char next = (char)((int)'a' + ci);
                    if (next != mem)
                    {
                        wordArray[i] = next;
                        String newWord = new String(wordArray);
                        if (dictionary.Contains(newWord))
                        {
                            words.Add(newWord);
                        }
                    }
                }
    
                wordArray[i] = mem;
            }
    
            return words;
        }
    }
    

Log in to reply
 

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