Maybe bug? Why TLE?It's only 55ms in my PC.


  • 0
    R

    Below is the code:(this code is according to the solution of Question127. For Q127, i got AC)

    public class Solution {
    public IList<IList<string>> FindLadders(string beginWord, string endWord, IList<string> wordList) {
    IList<IList<string>> result = new List<IList<string>>();
    if(beginWord == endWord)
    {
    result.Add(new List<string>() { beginWord });
    }
    else
    {
    HashSet<string> set = new HashSet<string>();
    foreach (var word in wordList)
    {
    set.Add(word);
    }

                bool stop = false;
                int length = beginWord.Length;
                HashSet<string> used = new HashSet<string>();
                Queue<string> q = new Queue<string>();
                Queue<List<string>> q2 = new Queue<List<string>>();
                q.Enqueue(beginWord);
                set.Remove(beginWord);
                List<string> rootList = new List<string>();
                rootList.Add(beginWord);
                used.Add(beginWord);
                q2.Enqueue(rootList);
                var transList = new List<string>();
                while (!stop && q.Any())
                {
                    int qCount = q.Count;
                    for (int i = 0; i < qCount; i++) // one level
                    {
                        string curr = q.Dequeue();
                        var curr2 = q2.Dequeue();
                        if (curr == endWord)//找到end,直接返回结果
                        {
                            stop = true;
                            result.Add(curr2);
                        }
                        else
                        {
                            var tempList = FindLaddersHelper(new StringBuilder(curr), set, used);
                            transList.AddRange(tempList);
                            foreach (var transWord in tempList)
                            {
                                q.Enqueue(transWord);
                                curr2.Add(transWord);
                                q2.Enqueue(new List<string>(curr2));
                                curr2.RemoveAt(curr2.Count - 1);
                            }
                        }
                    }
    
                    
                    transList.ForEach(t => used.Add(t));
                    transList.Clear();
                }
            }
    
            return result;
    }
    private List<string> FindLaddersHelper(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); 不在此处设为使用过,要在遍历完这一层的全部数据后,统一设置为使用过,(区别于LadderLengthHelper的逻辑)
                    }
                }
                word[i] = back;
            }
    
            return result;
        }
    

    }

    0_1486285322421_upload-0de3145a-08c3-4084-8320-cef2ba18a8cb


Log in to reply
 

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