Judging is wrong.


  • -2
    H
    var ladderLength = function(beginWord, endWord, wordList) {
        var tmpL1List = [], tmpL1Len;
        var nextMap, key;
        var count = 1;
        var i, j, tmpL2Map;
    
        tmpL1List.push(beginWord);
        while (tmpL1List.length) {
            count++;
            nextMap = {};
            for (i = 0, tmpL1Len = tmpL1List.length ; i < tmpL1Len ; i++) {
                tmpL2Map = get1DiffMap(tmpL1List[i], wordList);
                if (tmpL2Map[endWord]) return count;
                else {
                    for (key in tmpL2Map) {
                        if (check1Diff(key, endWord))
                            return count + 1;
                        else
                            nextMap[key] = key;
                    }
                }
            }
            reconstWordList(tmpL1List, wordList);
            tmpL1List = [];
            for (key in nextMap) {
                tmpL1List.push(key);
            }
        }
        return 0;
    };
    
    function reconstWordList(firstList, wordList) {
        var firstLen = firstList.length,
            wordLen,
            i, j;
        for (i = 0, wordLen = wordList.length ; i < wordLen ; i++) {
            for (j = 0 ; j < firstLen ; j++) {
                if (firstList[j] === wordList[i]) {
                    wordList.splice(i, 1);
                }
            }
        }
        return wordList;
    }
    
    function get1DiffMap(str, arr) {
        var result = {}, i, tmp, len = arr.length;
        for (i = 0 ; i < len ; i++) {
            tmp = arr[i];
            if (check1Diff(str, tmp)) {
                result[tmp] = tmp;
            }
        }
        return result;
    }
    
    function check1Diff(s1, s2) {
        var diffCount = 0, len = s1.length, i, tmp;
        for (i = 0 ; i < len ; i++) {
            if (s1.charAt(i) !== s2.charAt(i))
                diffCount++;
        }
        return diffCount === 1;
    }
    
    
    console.log(ladderLength('top', 'sky', ["ton","got","log", "son", "soy"]));
    console.log(ladderLength('top', 'sky', ["not","got","log", "toy", "son", "soy"]));
    console.log(ladderLength('hot', 'git', ["not","got","log"]));
    console.log(ladderLength('hot', 'big', ["not","got","log"]));
    console.log(ladderLength('a', 'b', ["a","b","c"]));
    console.log(ladderLength("a", "c", ["a","b","c"]));
    

    For the last test case, which is ("a", "c", ["a","b","c"]), this code actually produces the right answer 2 in browser or in node.js.
    But the leetcode judge says this code produces 0.

    I think leetcode judge is wrong.


  • 0

    I agree with you.


  • 0
    R
    This post is deleted!

  • 0
    D

    First of, how is 2 the right answer, is 1 not the right answer here?
    a can be transformed to c in 1 step.
    The expected solution is wrong.
    Submission Result: Wrong Answer More Details

    Input:
    "a"
    "c"
    ["a","b","c"]
    Output:
    1
    Expected:
    2


  • 0
    T

    My C# source code get into the same case.
    For case "a", "c", ["a","b","c"], the result in IDE is 2, however, the leetcode result is 0.

        public int LadderLength(string beginWord, string endWord, ISet<string> wordList)
        {
            Queue<string> queue = new Queue<string>();
            queue.Enqueue(beginWord);
            HashSet<string>visited = new HashSet<string>(){beginWord};
            int level = 1;
    
            while (queue.Count != 0)
            {
                int count = queue.Count;
                for (int i = 0; i < count; ++i)
                {
                    string cur = queue.Dequeue();
                    if (cur == endWord) return level;
    
                    char[] arr = cur.ToCharArray();
                    for (int j = 0; j < cur.Length; ++j)
                    {
                        for (char c = 'a'; c <= 'z'; ++c)
                        {
                            arr[j] = c;
                            string newStr = new String(arr);
                            if (wordList.Contains(newStr) && !visited.Contains(newStr))
                            {
                                queue.Enqueue(newStr);
                                visited.Add(newStr);
                            }
                        }
    
                        arr[j] = cur[j];
                    }
                }
    
                ++level;
            }
    
            return 0;
        }
    

Log in to reply
 

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