Word Ladder 运行时复杂度

Question

我正在尝试解决以下问题：

给定一个 beginWord，say pig，一个 endWord，say phi，以及一个单词列表 wordList，say [phg, phi]。 beginword每次允许改变一个字符，并且改变后的词需要在wordList中。我需要一种算法来找到实现转换的最少步骤。在我的示例中，我们可以执行 pig -> phg -> phi。而且所有涉及的单词都是相同的长度。

我的解决方案是使用 BFS：

queue;
level = 0;
queue.add(beginWord);
while(queue is not empty){
    for(i looping from 0 to the size of the queue){
        curr = the first element in the queue;
        if curr is endWord, then returns level + 1;
        for(j starting from 0 to the length of curr){
            for(c starting from a to z){
                replaced = replace the jth character of curr with c;
                if we have never seen replaced before and it is contained in wordList, then add it to the queue.
            }
        }
    }
}
return 0;

现在我正在努力想出这个算法的运行时复杂度。假设words的长度是$M$，wordList的长度是N。我的想法如下：

对于每个中间词，您有 26**M 个选择，在最坏的情况下，可能需要访问 wordList 中的所有 N 个词，因此总共有 N * 26 ** M 个。但是，由于我们要求所有转换都在 wordList 中，因此实际上，在每个中间词处，您最多有 N-1 个选择。因此，在我看来，运行时复杂度应该是 O(N(N - 1)).

对吗？我不这么认为，因为即使在每个中间词中，只有 N-1 种可能的转换，人们确实会花费操作来检查其中哪些 N-1 个是有效的，方法是遍历整个单词和用 26 种可能性替换了它的每个字符。

我知道问题已经被问过了here。但是那里没有答案，我不同意他们的分析。

Answer 1

所以就算法复杂度而言：

queue;
level = 0;
queue.add(beginWord);
while(queue is not empty){
    for(i looping from 0 to the size of the queue){
        curr = the first element in the queue;
        if curr is endWord, then returns level + 1;
        for(j starting from 0 to the length of curr){
            for(c starting from a to z){
                replaced = replace the jth character of curr with c;
                if we have never seen replaced before and it is contained in wordList, then add it to the queue.
            }
        }
    }
}
return 0;

假设最内层的循环使用 trie 或哈希表进行查找（不会比这更有效），内部条件需要 O(n):

while(queue is not empty){
    for(i looping from 0 to the size of the queue){
        curr = the first element in the queue;
        if curr is endWord, then returns level + 1;
        for(j starting from 0 to the length of curr){
            for(c starting from a to z){
                O(n)
            }
        }
    }
}

下一个最里面的循环迭代了26次，所以还是O(n):

while(queue is not empty){
    for(i looping from 0 to the size of the queue){
        curr = the first element in the queue;
        if curr is endWord, then returns level + 1;
        for(j starting from 0 to the length of curr){
            O(n)
        }
    }
}

下一个循环遍历字符串的长度，所以又是 n 步。额外的步骤要么是恒定时间的，要么是线性的（O(n)），所以我们可以忽略它们：

while(queue is not empty){
    for(i looping from 0 to the size of the queue){
        O(n ^ 2)
    }
}

这个 for 循环现在完全没用了。我们可以简单地删除它，而不是直接在 while 循环中轮询队列。 while 循环采用 O(m) 步，其中 m 是单词列表中的单词数。所以总的时间复杂度是 O(n^2 * m).

Word Ladder 运行时复杂度

Word Ladder runtime complexity

algorithm

time-complexity

code-complexity