c++ - 我的带内存的动态编程算法有什么问题？

Question

*抱歉我的英语不好。如果有任何您不明白的地方，请告诉我，以便我可以为您提供更多“有意义”的信息。

**这是第一次在 Stackoverflow 中提问。我在这里搜索了一些正确提问的规则，但应该有一些我遗漏的东西。我欢迎所有反馈。

我目前正在解决算法问题以提高我的技能，并且我在一个问题上挣扎了三天。本题来自https://algospot.com/judge/problem/read/RESTORE , 但是因为这个页面是韩文的，所以我试着把它翻译成英文。

问题
如果给定'k'个部分字符串，计算包含所有部分字符串的最短字符串。所有字符串仅包含小写字母。如果满足所有条件且长度相同的结果字符串超过 1 个，则选择任意一个字符串。

输入
在输入的第一行，给出了测试用例'C'(C<=50)的数量。对于每个测试用例，第一行给出部分字符串'k'(1<=k<=15)的数量，在接下来的k行中给出部分字符串。部分字符串的长度在1到40之间。

输出
对于每个测试用例，打印包含所有部分字符串的最短字符串。

示例输入
3
3
地理
王子
静
2
世界
你好
3
胡言乱语
卡达布拉
dabr

示例输出
地理
Hello World
死灵

这是我的代码。我的代码似乎与示例输入完美配合，当我为自己进行测试输入并进行测试时，一切正常。但是当我提交这段代码时，他们说我的代码是“错误的”。

请告诉我我的代码有什么问题。您不需要告诉我整个固定代码，我只需要导致我的代码出错的样本输入。添加了代码说明，使我的代码更易于理解。

代码说明

将所有输入的部分字符串保存在 vector “stringParts”中。
将当前最短字符串结果保存在全局变量“answer”中。
使用“缓存”数组进行内存 - 跳过重复的函数调用。

我设计的解决这个问题的算法分为两个函数—— restore() 和 eraseOverlapped()。

restore() 函数计算包含“stringParts”中所有部分字符串的最短字符串。
resotre() 的结果保存在“answer”中。

对于 restore()，有三个参数 - 'curString'、'selected' 和 'last'。
'curString' 代表当前选择和重叠的字符串结果。
'selected' 代表'stringParts' 当前被选中的元素。使用位掩码使我的算法简洁。
'last' 代表 'stringParts' 的最后一个选定元素，用于制作 'curString'。

eraseOverlapped() 函数进行预处理 - 它删除“stringParts”的元素，这些元素在执行 restore() 之前可以完全包含到其他元素中。

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#define MAX 15
using namespace std;

int k;
string answer; // save shortest result string

vector<string> stringParts;
bool cache[MAX + 1][(1 << MAX) + 1]; //[last selected string][set of selected strings in Bitmask]

void restore(string curString, int selected=0, int last=0) {
    //base case 1
    if (selected == (1 << k) - 1) {
        if (answer.empty() || curString.length() < answer.length()) 
            answer = curString;
        return;
    }
    //base case 2 - memoization
    bool& ret = cache[last][selected];
    if (ret != false) return;

    for (int next = 0; next < k; next++) {
        string checkStr = stringParts[next];
        if (selected & (1 << next)) continue;

        if (curString.empty())
            restore(checkStr, selected + (1 << next), next + 1);
        else {
            int check = false;
            //count max overlapping area of two strings and overlap two strings.
            for (int i = (checkStr.length() > curString.length() ? curString.length() : checkStr.length())
                ; i > 0; i--) {
                if (curString.substr(curString.size()-i, i) == checkStr.substr(0, i)) {
                    restore(curString + checkStr.substr(i, checkStr.length()-i), selected + (1 << next), next + 1);
                    check = true;
                    break;
                }
            }
            if (!check) { // if there aren't any overlapping area
                restore(curString + checkStr, selected + (1 << next), next + 1);
            }
        }
    }
    ret = true;
}
//check if there are strings that can be completely included by other strings, and delete that string.
void eraseOverlapped() {
    //arranging string vector in ascending order of string length
    int vectorLen = stringParts.size();
    for (int i = 0; i < vectorLen - 1; i++) {
        for (int j = i + 1; j < vectorLen; j++) {
            if (stringParts[i].length() < stringParts[j].length()) {
                string temp = stringParts[i];
                stringParts[i] = stringParts[j];
                stringParts[j] = temp;
            }
        }
    }

    //deleting included strings
    vector<string>::iterator iter;
    for (int i = 0; i < vectorLen-1; i++) {
        for (int j = i + 1; j < vectorLen; j++) {
            if (stringParts[i].find(stringParts[j]) != string::npos) {
                iter = stringParts.begin() + j;
                stringParts.erase(iter);
                j--;
                vectorLen--;
            }
        }
    }
}

int main(void) {
    int C;
    cin >> C; // testcase
    for (int testCase = 0; testCase < C; testCase++) {
        cin >> k; // number of partial strings
        memset(cache, false, sizeof(cache)); // initializing cache to false
        string inputStr;
        for (int i = 0; i < k; i++) {
            cin >> inputStr;
            stringParts.push_back(inputStr);
        }
        eraseOverlapped();
        k = stringParts.size();

        restore("");
        cout << answer << endl;
        answer.clear();
        stringParts.clear();
    }
}

Answer 1

在确定哪些字符串部分可以从列表中删除，因为它们包含在其他字符串部分中，对此问题建模的一种方法可能是“taxicab ripoff problem”问题(或最大 TSP)，其中每个潜在的通过重叠减少的长度被赋予正权重。考虑到问题中的输入量非常小，他们似乎希望有一个接近蛮力的解决方案，可能带有一些启发式和回溯或其他形式的内存。