Abbreviation

• Time : O(nm)
• Space : O(nm)

int dp[1001][1001];

bool helper(string& a, string& b, int i, int j) {
    if(dp[i][j] != -1) return dp[i][j];
    int& res = dp[i][j] = 0;
    if(j == b.length()) {
        for(int aa = i; aa < a.length(); aa++)
            if(isupper(a[aa])) return res;
        return res = 1;
    }
    if(i == a.length()) return res;
    if(a[i] == b[j]) return res = helper(a, b, i + 1, j + 1);
    if(islower(a[i]) and toupper(a[i]) == b[j]) return res = max(helper(a, b, i + 1, j + 1), helper(a, b, i + 1, j));
    if(islower(a[i])) return res = helper(a, b, i + 1, j);
    return res;
}

string abbreviation(string a, string b) {
    memset(dp, -1, sizeof dp);
    return helper(a, b, 0, 0) ? "YES" : "NO";
}