Сложность времени выполнения Word Ladder

Я пытаюсь решить следующую проблему:

Даны beginWord, скажем, pig, и endWord, скажем, phi, и список слов wordList, скажем, [phg, phi]. Нам разрешено каждый раз изменять один символ начального слова, и преобразованное слово должно быть в списке слов. Мне нужен алгоритм, чтобы найти минимальные шаги для достижения преобразования. В моем примере мы можем сделать 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;

Теперь я изо всех сил пытаюсь придумать сложность этого алгоритма во время выполнения. Предположим, что длина слов равна $M$, а длина списка слов равна N. Я думаю следующее:

Для каждого промежуточного слова у вас есть 26**M вариантов, и в худшем случае вам может понадобиться посетить все N слова в списке слов, так что всего вы получите N * 26 ** M. Однако, поскольку мы требуем, чтобы все преобразования были в списке слов, фактически для каждого промежуточного слова у вас есть не более N-1 вариантов. Таким образом, мне кажется, что сложность выполнения должна быть O(N(N - 1)).

Это правильно? Я так не думаю, потому что, несмотря на то, что в каждом промежуточном слове есть только N-1 возможных преобразований, нужно провести операции, чтобы проверить, какие N-1 из них действительны, перебирая все слово и заменяя каждый из его символов 26 возможностями. .

Я знаю, что проблема задана здесь. Но там не принимается никакого ответа, и я не согласен с их анализом.


algorithm time-complexity code-complexity
person penny    schedule 20.11.2020    source источник
comment
26**M представляет каждое возможное слово с M буквами. Но вы не ищете каждое возможное слово. Вы меняете только одну букву, поэтому возможных следующих слов всего 25 * M.   -  person user3386109    schedule 21.11.2020

Ответы (1)


arrow_upward
2
arrow_downward

Итак, что касается сложности алгоритма:

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).

person Paul    schedule 21.11.2020