Accepted c# solution


  • 0
    R

    public class Solution {
    public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
    if (beginWord == endWord)
    return 1;

            HashSet<string> set = new HashSet<string>();
            foreach(var word in wordList)
            {
                set.Add(word);
            }
    
            int length = beginWord.Length;
            HashSet<string> used = new HashSet<string>();
            Queue<string> q = new Queue<string>();
            q.Enqueue(beginWord);
            set.Remove(beginWord);
            used.Add(beginWord);
    
            int result = 1;
            while(q.Any())
            {
                result++;
                int qCount = q.Count;
                for(int i =0;i<qCount;i++) // one level
                {
                    string curr = q.Dequeue();
                    if (curr == endWord)//find endWord,return result-1
                    {
                        return result-1;
                    }
                    else
                    {
                        foreach (var transWord in LadderLengthHelper(new StringBuilder(curr), set, used))
                        {
                            q.Enqueue(transWord);
                        }
                    }
                }
            }
    
            return 0;
    }
        // 获取在set中存在的,跟word差一个字母的List
        private List<string> LadderLengthHelper(StringBuilder word, HashSet<string> set, HashSet<string> used)
        {
            List<string> result = new List<string>();
            for(int i =0;i<word.Length;i++)
            {
                char back = word[i];
                for(char c = 'a';c<='z';c++)
                {
                    word[i] = c;
                    var temp = word.ToString();
                    if (set.Contains(temp) && !used.Contains(temp))
                    {
                        result.Add(temp);
                        used.Add(temp);
                    }
                }
                word[i] = back;
            }
    
            return result;
        }
    

    }


Log in to reply
 

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