Блог

Словарная лестница
Учитывая два слова (начало и конец) и словарь,
найдите всю кратчайшую последовательность преобразований от начала до конца,
такое, что:
Одновременно можно изменять только одну букву, Каждое промежуточное слово должно существовать в словаре

Например,
Дано: start = «попадание«,
end = «винтик«,
dict = [«горячий», «точка», «собака», «лот», «журнал»]
Возврат

 [ 
  ["hit","hot","dot","dog","cog"], 
  ["hit","hot","lot","log","cog"]
]
  

Примечание:
Все слова имеют одинаковую длину.
Все слова содержат только строчные буквенные символы.

Лично я думаю, что временная сложность для этого алгоритма зависит от входных данных (start, end, dict), не может быть записана как временная сложность = O (?).

---

Спасибо AbcAeffchen. Временная сложность = O (len* N * (26 ^ (N / 2))), len — длина заданной начальной строки (или конечной строки), N — количество элементов dict.(Предположим, что C unordered_set реализован с помощью has set). Пожалуйста, ознакомьтесь с деталями ниже.

Идея этого решения: BFS (Map) DFS.[C ]

 #include <vector>
#include <unordered_map>
#include <deque>
#include <string>
using namespace std;

struct Node {
    string val;
    int level;
    vector<Node *> prevs;
    Node (string val, int level): val(val), level(level) {};
};

class Solution {
public:
vector<vector<string>> findLadders(string start, string end, unordered_set<string> amp;dict) {
    vector<vector<string>> list;

    // Input validation.
    if (start.compare(end) == 0) {
        vector<string> subList = {start, end};
        list.push_back(subList);
        return list;
    }

    deque<string> queue;
    unordered_map<string, Node *> map;

    queue.push_back(start);
    Node *start_node = new Node(start, 0);
    map.emplace(start, start_node);

    while (!queue.empty()) {
        // Dequeue.
        string curr_string = queue.front();
        queue.pop_front();

        Node *curr_node = map.find(curr_string)->second;
        int curr_level = curr_node->level;

        int len = curr_string.length();

        if (curr_string.compare(end) == 0) {
            // Find the end.
            vector<string> subList;
            subList.push_back(curr_node->val);

            getAllPathes(curr_node, list, subList);

            return list;
        }

        // Iterate all children.
        for (int i = 0; i < len; i   ) {
            char curr_original_char = curr_string[i];

            // Have a try.
            for (char c = 'a'; c <= 'z'; c   ) {
                if (c == curr_original_char) continue;
                curr_string[i] = c;

                if (dict.find(curr_string) != dict.end()) {
                    if (map.find(curr_string) == map.end()) {
                        // The new string has not been visited.
                        Node *child = new Node(curr_string, curr_level   1);

                        // Add the parents of the current into prevs.
                        child->prevs.push_back(curr_node);

                        // Enqueue.
                        queue.push_back(curr_string);
                        map.emplace(curr_string, child);
                    } else {
                        // The new string has been visited.
                        Node *child = map.find(curr_string)->second;

                        if (child->level == curr_level   1) {
                            child->prevs.push_back(curr_node);
                        }
                    }
                }
            }

            // Roll back.
            curr_string[i] = curr_original_char;
        }
    }

    return list;
}

void getAllPathes(Node *end, vector<vector<string>> amp;list, vector<string> amp;subList) {
    // Base case.
    if (end == NULL) {
        // Has been get to the top level, no topper one.
        vector<string> one_rest(subList);
        list.push_back(one_rest);
        return;
    }

    vector<Node *> prevs = end->prevs;

    if (prevs.size() > 0) {
        for (vector<Node *>::iterator it = prevs.begin();
             it != prevs.end(); it   ) {

            // Have a try.
            subList.insert(subList.begin(), (*it)->val);         

            // Do recursion.
            getAllPathes((*it), list, subList);

            // Roll back.
            subList.erase(subList.begin());
        }

    } else {
        // Do recursion.
        getAllPathes(NULL, list, subList);
    }
}
};
  

Разделение

Давайте разделим сложность на три части:

1. Найдите следующее слово в последовательности преобразования
2. Длина кратчайшей последовательности преобразований
3. Количество последовательностей преобразования

Предположения

Пусть n — длина заданных слов и N количество слов в словаре. Давайте также предположим, что словарь отсортирован.

1. Часть

Затем вы можете найти следующее слово по O(n ⋅ 26 ⋅ log(N)) = O(n log N) шагам.

• n символы в вашем word, которые можно изменить.
• 26 возможные изменения для каждого символа.
• log(N) посмотреть, существует ли это слово в словаре.

2. Часть

Какой длины может быть кратчайшая последовательность преобразования?

Пример: Пусть начальным словом будет «aa», конечным словом «zz» и словарем
[«ab», «bb», «bc», «cc», ..].
В этом примере требуется 26 преобразований. Я думаю, вы можете создать входные данные в наихудшем случае, для которых требуется что-то вроде 26^n-1 преобразований.

Но это зависит от слов в словаре. Итак, наихудшим случаем будет N , т.Е. используются все слова в словаре.

3. Часть

Сколько существует различных последовательностей?

Каждый раз, когда вы ищете следующее слово в последовательности, можно найти 26 различных следующих шагов. Но только для первой половины длины кратчайшей последовательности, потому что это справедливо также при переключении начального и конечного слов. Таким образом, может быть до O(26N/2) разных последовательностей, при условии, что длина кратчайшей последовательности в наихудшем случае равна O(N) .

Краткие сведения

• O(n log N) нахождение следующего преобразования в последовательности.
• O(N) преобразования для каждой последовательности
• O(26N/2) разные последовательности.

В итоге вы получаете O(26N/2 N log N) .

УВЕДОМЛЕНИЕ

• Это справедливо, только если ваш словарь может содержать любую последовательность символов в виде «слов». Если вы допускаете только слова, которые существуют в реальном языке, вы можете использовать статистику для доказательства большей сложности.
• Длина кратчайшей последовательности коррелирует с количеством различных последовательностей. Если у вас в словаре много слов, последовательность может стать очень длинной, но если у вас их слишком много, вы, возможно, получите больше разных последовательностей, но они также станут короче. Возможно, можно использовать некоторую статистику, чтобы доказать здесь также лучшую сложность.

Я надеюсь, что это поможет