Another C# BFS ETL Solution without Queue


  • 0
    L
    public int LadderLength(string beginWord, string endWord, ISet<string> wordDict)
        {
            HashSet<string> words = new HashSet<string>();
            words.Add(beginWord);
            int count = 1;
            while(words.Count > 0)
            {
                words = nextWords(words, wordDict, endWord);
                count++;
                if (words.Contains(endWord)) return count;
            }
            return 0;
        }
    
        private HashSet<string> nextWords(HashSet<string> lastBeginWords, ISet<string> wordDict, string endWord)
        {
            HashSet<string> newBeginWords = new HashSet<string>();
            foreach (string str in lastBeginWords)
            {
                if (endWord.Length != str.Length) continue;
                int iDiff = 0;
                for (int i = 0; i < str.Length; i++)
                {
                    if (iDiff > 1) break;
                    if (str[i] != endWord[i]) iDiff++;
                }
                if (iDiff == 1)
                {
                    newBeginWords.Add(endWord);
                    return newBeginWords;
                }
                foreach (string word in wordDict)
                {
                    if (word.Length != str.Length) continue;
                    iDiff = 0;
                    for(int i = 0; i < str.Length; i++)
                    {
                        if (iDiff > 1) break;
                        if (str[i] != word[i]) iDiff++;
                    }
                    if (iDiff == 1 && !lastBeginWords.Contains(word))
                        newBeginWords.Add(word);
                }
            }
            foreach(string word in newBeginWords)
                wordDict.Remove(word);
            return newBeginWords;
        }

Log in to reply
 

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