LC943 WA

class Solution
{
    int check_suffix(const string &str, const string &suffix)
    {
        int strlen = str.size();
        int sfxlen = suffix.size();
        int mlen = min(strlen, sfxlen);
        for (int i = mlen; i >= 0; --i) {
            if (str.substr(strlen - i) == suffix.substr(0, i))
                return i;
        }
        return 0;
    }

  public:
    string shortestSuperstring(vector<string> &words)
    {
        int n = words.size();
        // vector<string> dp(1 << n);
        auto dp = vector<vector<string>>(n, vector<string>(1 << n));
        // auto dp = vector<string>(1 << n);
        for (int i = 0; i < n; ++i) {
            dp[i][1 << i] = words[i];
        }
        int state = (1 << n);
        string ans = "";
        for (int i = 0; i < n; ++i) {
            for (int s = 0; s < state; ++s) {
                if ((s & (1 << i)) == 0 || dp[i][s] == "")
                    continue;
                for (int j = 0; j < n; ++j) {
                    if ((s | (1 << j)) == s) {
                        continue;
                    }
                    int ns = s | (1 << j);
                    int suffix = check_suffix(dp[i][s], words[j]);
                    string res = dp[i][s] + words[j].substr(suffix);
                    dp[j][ns] = (dp[j][ns] == "" ? res : (res.size() < dp[j][ns].size() ? res : dp[j][ns]));
                    if (ns == state - 1)
                        ans = (ans == "" ? dp[j][ns] : (ans.size() < dp[j][ns].size() ? ans : dp[j][ns]));
                }
            }
        }
        return ans;
    }
};