OJ bug for test case: "a", "c", ["a","b","c"], with C#


  • 0
    A

    The solution is a combination of BFS and backtracking. The OJ failed the test case "a", "c", ["a","b","c"]. It works perfect fine on my local box with Visual Studio. I came up with a FIX by adding the first line commented out to pass OJ, but it doesn't make sense. Anyone has any idea?

        static void Main(string[] args)
        {
            Solution sol = new Solution();
    
            var x = sol.LadderLength("a", "c", (new HashSet<string>(new string[] { "a", "b", "c" }.ToList())));
        }
    
        public int LadderLength(string beginWord, string endWord, ISet<string> wordList)
        {
            //wordList.Add(endWord); //without this line, this test case fails: "a", "c", ["a","b","c"] with OJ
    
            int ladderL = 0;
            int min = int.MaxValue;
    
            Queue<string> q = new Queue<string>();
            q.Enqueue(beginWord);
            wordList.Remove(beginWord);
    
            while (q.Count() != 0)
            {
                ladderL++;
                var x = q.Count();
                for (int i = 0; i < x; i++)
                {
                    string wordDQed = q.Dequeue();
                    StringBuilder sb = new StringBuilder(wordDQed);
                    for (int j = 0; j < wordDQed.Length; j++)
                    {
                        for (int c = 'a'; c <= 'z'; c++)
                        {
                            if (wordDQed[j] != c)
                            {
                                sb[j] = (char)c;
                                var word = sb.ToString();
                                if (wordList.Contains(word))
                                {
                                    if (word == endWord)
                                    {
                                        if (min > ladderL + 1) min = ladderL + 1;
                                    }
                                    else
                                    {
                                        q.Enqueue(word);
                                        wordList.Remove(word);
                                    }
                                }
                            }
                        }
                        sb[j] = wordDQed[j];//backtracking for each position
                    }
                }
            }
    
            return min == int.MaxValue ? 0 : min;
        }

  • 0
    V

    I'm confused. "a" can directly be changed to "c", why would it have to go through "b" in order to do that?!


  • 0
    V

    Never mind, it's the number of nodes.


  • 0
    W

    +1, I can repro


  • 0
    K

    It seems to me that the implementation of the ISet<string> interface that is passed via wordList is buggy. It doesn't seem to behave like e.g. a regular HashSet<string>. Is it possible to view the implementation of test cases?


  • 0
    G

    +1 to that
    Input
    "a"
    "c"
    ["a","b","c"]
    when executed locally returns 2, But OJ returns 1.


Log in to reply
 

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