LC943 TLE

class Solution
{
    vector<vector<int>> suff_len;
    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;
    }
    int n;
    vector<vector<string>> dp;
    int lowbit(int x) { return x ^ -x; }

    string search(int node, int state, const vector<string> &ws)
    {
        if (dp[node][state] != "")
            return dp[node][state];
        int prev_state = state ^ (1 << node);
        string ans = "";
        for (int i = 0; i < n; ++i) {
            if (((1 << i) | prev_state) == prev_state) {
                string opt = search(i, prev_state, ws);
                // int suffix = check_suffix(opt, ws[node]);
                int suffix = suff_len[i][node];
                string ans2 = opt + ws[node].substr(suffix);
                if (ans == "")
                    ans = ans2;
                ans = ans.size() < ans2.size() ? ans : ans2;
            }
        }

        return dp[node][state] = ans;
    }

  public:
    string shortestSuperstring(vector<string> &words)
    {
        n = words.size();
        dp = vector<vector<string>>(n, vector<string>(1 << n));
        for (int i = 0; i < n; ++i) {
            dp[i][1 << i] = words[i];
        }
        int state = (1 << n);
        suff_len = vector<vector<int>>(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j)
                    continue;
                suff_len[i][j] = check_suffix(words[i], words[j]);
            }
        }

        string ans = search(0, state - 1, words);
        for (int i = 1; i < n; ++i) {
            string opt = search(i, state - 1, words);
            ans = ans.size() < opt.size() ? ans : opt;
        }
        return ans;
    }
};