c++ - 该算法获取所有字梯的时间复杂度是多少？

Question

Word Ladder
Given two words (start and end), and a dictionary,
find all shortest transformation sequence(s) from start to end,
such that:
Only one letter can be changed at a time Each intermediate word must exist in the dictionary

For example,
Given: start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return

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

Note:
All words have the same length.
All words contain only lowercase alphabetic characters.

---

Personally I think, the time complexity for this algorithm depends on the input(start, end, dict), can not write out like time complexity = O(?).

---

Thank you AbcAeffchen. The tight time complexity = O(len*N*(26^(N/2))), len is the length of the given start string(or end string), N is the number of elements of the dict.(Assume C++ unordered_set is implemented by has set). Pleas check details below.

这个方案的思路: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词典中单词的数量。我们还假设字典已排序。

1。部分

然后你可以在O(n ⋅ 26 ⋅ log(N)) = O(n log N)中找到下一个词步骤。

• n单词中的字符，可以更改。
• 26每个角色可能发生的变化。
• log(N)查找，如果这个词存在于字典中。

2。部分

最短的转换序列可以有多长？

示例:让起始词为“aa”，结束词为“zz”和字典
[“ab”、“bb”、“bc”、“cc”、..]。
此示例需要 26 次转换。我认为您可以构建需要类似 26^n-1 转换的最坏情况输入。

但这要看字典里的单词。所以最坏的情况是N ， IE。字典中的所有单词都被使用。

3。部分

存在多少种不同的序列？

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

总结

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

你总共得到 O(26<sup>N/2</sup> N log N) .

通知

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

希望对你有帮助