c++ - 字符串解码 : looking for a better approach

Question

我已经为该问题制定了 O(n 平方) 的解决方案。我想知道一个更好的解决方案。 (这不是作业/面试问题，而是我出于自己的兴趣而做的事情，因此在这里分享):

If a=1, b=2, c=3,….z=26. Given a string, find all possible codes that string
can generate. example: "1123" shall give:
aabc //a = 1, a = 1, b = 2, c = 3
kbc // since k is 11, b = 2, c= 3
alc // a = 1, l = 12, c = 3
aaw // a= 1, a =1, w= 23
kw // k = 11, w = 23

这是我的问题代码:

void alpha(int* a, int sz, vector<vector<int>>& strings) {
    for (int i = sz - 1; i >= 0; i--) {
        if (i == sz - 1) {
            vector<int> t;
            t.push_back(a[i]);
            strings.push_back(t);
        } else {
            int k = strings.size();

            for (int j = 0; j < k; j++) {
                vector<int> t = strings[j];
                strings[j].insert(strings[j].begin(), a[i]);

                if (t[0] < 10) {
                   int n = a[i] * 10 + t[0];

                    if (n <= 26) {
                        t[0] = n;
                        strings.push_back(t);
                    }
                }
            }
        }
    }
}

本质上， vector 字符串将保存数字集。这将在 n 广场运行。我正在尝试至少一个 nlogn 解决方案。

直觉上 tree 应该在这里有所帮助，但不会得到任何结果。

Answer 1

通常，您的问题复杂度更像是2^n，而不是n^2，因为您的k 会随着每次迭代而增加。

这是另一种递归解决方案(注意:递归对于非常长的代码是不利的)。我没有专注于优化，因为我不是最新的 C++X，但我认为递归解决方案可以通过一些 move 来优化。

与迭代解决方案相比，递归还使复杂性更加明显。

// Add the front element to each trailing code sequence. Create a new sequence if none exists
void update_helper(int front, std::vector<std::deque<int>>& intermediate)
{
    if (intermediate.empty())
    {
        intermediate.push_back(std::deque<int>());
    }
    for (size_t i = 0; i < intermediate.size(); i++)
    {
        intermediate[i].push_front(front);
    }
}

std::vector<std::deque<int>> decode(int digits[], int count)
{
    if (count <= 0)
    {
        return std::vector<std::deque<int>>();
    }

    std::vector<std::deque<int>> result1 = decode(digits + 1, count - 1);
    update_helper(*digits, result1);

    if (count > 1 && (digits[0] * 10 + digits[1]) <= 26)
    {
        std::vector<std::deque<int>> result2 = decode(digits + 2, count - 2);

        update_helper(digits[0] * 10 + digits[1], result2);

        result1.insert(result1.end(), result2.begin(), result2.end());
    }

    return result1;
}

调用:

std::vector<std::deque<int>> strings = decode(codes, size);

编辑:

关于原始代码的复杂性，我将尝试展示在最坏情况下会发生什么，其中代码序列仅由 1 和 2 组成值(value)观。

void alpha(int* a, int sz, vector<vector<int>>& strings)
{
    for (int i = sz - 1;
        i >= 0;
        i--)
    {
        if (i == sz - 1)
        {
            vector<int> t;
            t.push_back(a[i]);
            strings.push_back(t); // strings.size+1
        } // if summary: O(1), ignoring capacity change, strings.size+1
        else
        {
            int k = strings.size();

            for (int j = 0; j < k; j++)
            {
                vector<int> t = strings[j]; // O(strings[j].size) vector copy operation

                strings[j].insert(strings[j].begin(), a[i]); // strings[j].size+1
                // note: strings[j].insert treated as O(1) because other containers could do better than vector

                if (t[0] < 10)
                {
                    int n = a[i] * 10 + t[0];

                    if (n <= 26)
                    {
                        t[0] = n;
                        strings.push_back(t); // strings.size+1
                        // O(1), ignoring capacity change and copy operation

                    } // if summary: O(1), strings.size+1

                } // if summary: O(1), ignoring capacity change, strings.size+1

            } // for summary: O(k * strings[j].size), strings.size+k, strings[j].size+1

        } // else summary: O(k * strings[j].size), strings.size+k, strings[j].size+1

    } // for summary: O(sum[i from 1 to sz] of (k * strings[j].size))
    // k (same as string.size) doubles each iteration => k ends near 2^sz
    // string[j].size increases by 1 each iteration
    // k * strings[j].size increases by ?? each iteration (its getting huge)
}

也许我在某处犯了一个错误，如果我们想玩得更好，我们可以将 vector 拷贝视为 O(1) 而不是 O(n)，以便降低复杂性，但仍然存在一个铁的事实，即最坏的情况是在内部循环的每次迭代中将外部 vector 大小加倍(至少每第 2 次迭代，考虑到 if 条件的确切结构)和内部循环取决于不断增长的 vector 大小，这使得整个故事至少为 O(2^n)。

编辑2:

我算出了结果复杂度(最好的假设算法仍然需要创建结果的每个元素，所以结果复杂度就像是任何算法可以达到的下限)

它实际上遵循斐波那契数列:

对于大小 N+2 的最坏情况输入(比如只有 1)，您有:

• 大小 N 有 k(N) 个元素
• 大小 N+1 有 k(N+1) 个元素
• size N+2 是以 a 开头的代码组合，后跟 size N+1 的组合(a 取源的一个元素)和以 k 开头的代码，后跟 size N 的组合(k 取两个来源的元素)
• 大小 N+2 有 k(N) + k(N+1) 个元素

从 size 1 => 1 (a) 和 size 2 => 2 (aa or k) 开始

结果:仍然呈指数增长；)

编辑3:

基于 Edit2 中解释的属性，制定了一个动态编程解决方案，有点类似于您对代码数组进行反向迭代的方法，并在其 vector 使用方面进行了某种优化。

内部循环 (update_helper) 仍然由结果计数(最坏的斐波那契数列)主导，一些外部循环迭代将有相当数量的子结果，但至少子结果- 结果被简化为指向某个中间节点的指针，因此复制应该非常有效。作为一个小奖励，我将结果从数字转换为字符。

另一个编辑:将范围 0 - 25 的代码更新为 'a' - 'z'，修复了一些导致错误结果的错误。

struct const_node
{
    const_node(char content, const_node* next)
        : next(next), content(content)
    {
    }

    const_node* const next;
    const char content;
};

// put front in front of each existing sub-result
void update_helper(int front, std::vector<const_node*>& intermediate)
{
    for (size_t i = 0; i < intermediate.size(); i++)
    {
        intermediate[i] = new const_node(front + 'a', intermediate[i]);
    }
    if (intermediate.empty())
    {
        intermediate.push_back(new const_node(front + 'a', NULL));
    }
}

std::vector<const_node*> decode_it(int digits[9], size_t count)
{
    int current = 0;
    std::vector<const_node*> intermediates[3];
    for (size_t i = 0; i < count; i++)
    {
        current = (current + 1) % 3;
        int prev = (current + 2) % 3; // -1
        int prevprev = (current + 1) % 3; // -2

        size_t index = count - i - 1; // invert direction

        // copy from prev
        intermediates[current] = intermediates[prev];
        // update current (part 1)
        update_helper(digits[index], intermediates[current]);

        if (index + 1 < count && digits[index] &&
            digits[index] * 10 + digits[index + 1] < 26)
        {
            // update prevprev
            update_helper(digits[index] * 10 + digits[index + 1], intermediates[prevprev]);
            // add to current (part 2)
            intermediates[current].insert(intermediates[current].end(), intermediates[prevprev].begin(), intermediates[prevprev].end());
        }
    }
    return intermediates[current];
}

void cleanupDelete(std::vector<const_node*>& nodes);

int main()
{
    int code[] = { 1, 2, 3, 1, 2, 3, 1, 2, 3 };
    int size = sizeof(code) / sizeof(int);
    std::vector<const_node*> result = decode_it(code, size);

    // output
    for (size_t i = 0; i < result.size(); i++)
    {
        std::cout.width(3);
        std::cout.flags(std::ios::right);
        std::cout << i << ": ";
        const_node* item = result[i];
        while (item)
        {
            std::cout << item->content;
            item = item->next;
        }
        std::cout << std::endl;
    }

    cleanupDelete(result);
}


void fillCleanup(const_node* n, std::set<const_node*>& all_nodes)
{
    if (n)
    {
        all_nodes.insert(n);
        fillCleanup(n->next, all_nodes);
    }
}

void cleanupDelete(std::vector<const_node*>& nodes)
{
    // this is like multiple inverse trees, hard to delete correctly, since multiple next pointers refer to the same target
    std::set<const_node*> all_nodes;
    for each (auto var in nodes)
    {
        fillCleanup(var, all_nodes);
    }
    nodes.clear();
    for each (auto var in all_nodes)
    {
        delete var;
    }
    all_nodes.clear();
}

动态重用结构的一个缺点是清理，因为您要小心地只删除每个节点一次。