该算法获取所有词梯的时间复杂度是多少？

Question

单词梯形
给定两个单词（开始和结束）和一个字典，
查找从开始到结束的所有最短转换序列，
以便:
每次只能更改一个字母，每个中间单词必须存在于字典中

例如，
给定:start=“hit”
end=“cog”
dict=[“hot”,“dot”,“dog”,“lot”,“log”]
返回

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

注意:
所有单词长度相同。
所有单词只包含小写字母字符。

我个人认为，这个算法的时间复杂度取决于输入(start，end，dict)，不能写出像时间复杂度=O（？）。

这个解决方案的思想: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> &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>> &list, vector<string> &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);
    }
}
};

Answer 1

让我们将其复杂性分为三个部分：

1. 在转换序列中查找下一个单词
2. 最短变换序列的长度
3. 变换序列的个数

设n是给定单词的长度，n是字典中的单词数。我们还假设字典是排序的。

然后，您可以在O(n8·26·log(n))=O(n log n)步骤中找到下一个单词。

• n单词中可以更改的字符。
• 26每个字符可能发生的更改。
• 日志(N)要查找，如果字典中存在此单词。

一个最短的转化序列能有多长？

示例：让开始词是“aa”，结束词是“zz”，字典
[“ab”，“bb”，“bc”，“cc”，..]。
这个示例需要26次转换。我认为您可以构建需要26^n-1转换的最坏情况输入。

但这取决于字典里的单词。所以最坏的情况是n，即。字典里的词都用上了。

存在多少种不同的序列？

每次你在顺序中寻找下一个单词时，都有可能找到26个不同的下一个步骤。但只适用于最短序列的前半部分，因为如果切换开始和结束词，这也适用。因此，最多可以有O(26N/2)不同的序列，只要最短序列的最坏情况是O(N)。

• O(n log n)查找序列中的下一个转换。
• O(N)每个序列的转换
• O(26N/2)不同序列。

总共得到O(26N/2N log N)。

• 只有当您的字典可以包含任何字符序列作为“单词”时，这才成立。如果只允许真实语言中存在的单词，则可以使用统计数据来证明更好的复杂性。
• 最短序列的长度与不同序列的个数有关。如果你的字典里有很多单词，序列可能会变得很长，但如果你有太多的话，你可能会得到更多不同的序列，但它们也会变得更短。也许我们可以在这里用一些统计数据来证明更好的复杂性。

我希望这能有所帮助