Match Left and Right
We first match strings right-to-left, dp[i] tells us the number of matched characters starting from i.\n\nThen, we match characters left-to-right.  \n\nIf we se
We first match strings right-to-left, `dp[i]` tells us the number of matched characters starting from `i`.\n\nThen, we match characters left-to-right.  \n\nIf we see a mismatch, and the sum of:\n- matched characters so far,\n- number of remaining `wild` characters (one for this problem),\n- matched characters on the right (`dp[i + 1]`), \n\nis greater or equal to `len(w2)`, we use a wild character.\n\nNote that this solution should also work if the number of wild characters is greater than 1.\n\n**C++**\n```cpp\nvector<int> validSequence(const string &w1, const string &w2) {\n    int sz1 = w1.size(), sz2 = w2.size(), wild = 1;\n    vector<int> dp(w1.size() + 1), res;\n    for (int i = sz1 - 1, j = sz2 - 1; i >= 0; --i) {\n        dp[i] = dp[i + 1] + (j >= 0 && w1[i] == w2[j]);\n        j -= j >= 0 && w1[i] == w2[j]; \n    }\n    bool found = false;\n    for (int i = 0; i < sz1 && res.size() < sz2; ++i) {\n        if (w1[i] == w2[res.size()])\n            res.push_back(i);\n        else if (wild && res.size() + wild + dp[i + 1] >= sz2) {\n            --wild;\n            res.push_back(i);\n        }\n    }\n    return res.size() == sz2 ? res : vector<int>{};\n}\n```
['C']