• + 0 comments

    tricky question. the naive dynamic programming 2D matrix method takes O(a.size()^2 * b.size()), which will likely give time out, but with modification can do it in O(a.size() * b.size()) time

    string abbreviation(string a, string b) {
        vector<vector<bool>> M(a.size()+1, vector<bool>(b.size()+1));
        int upperCase = 0;
        M[0][0] = true;
        for (int i=1; i < a.size()+1; i++) {
            if (isupper(a[i-1])) upperCase++;
            if (upperCase == 0) M[i][0] = true;
        }
        for (int j=1; j < b.size()+1; j++) {
            for (int i=j; i < a.size()+1; i++) {
                if (M[i-1][j] == false or isupper(a[i-1])) M[i][j] = (M[i-1][j-1] and toupper(a[i-1]) == b[j-1]);
                else M[i][j] = true;
            }
        }
        return M[a.size()][b.size()] ? "YES" : "NO";
    }