Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.4 kB
1
Indexable
Never
int firstCh;
long long mem[1010][30];

long long dp(int idx, int prevCh, string& s) {
    if(idx == s.size()-1) {
        if(prevCh != firstCh) {
            return 1;
        }
        return 0;
    }
    long long ans = 0;
    long long mod = 1e9 + 7;
    if(mem[idx][prevCh] != -1) {
        return mem[idx][prevCh];
    }
    if(s[idx] == '?') {
        for(int ch = 0; ch < 26; ch++) {
            if(ch != prevCh) {
                ans += dp(idx+1, ch, s);
                ans %= mod;
            }
        }
    }
    else {
        if(s[idx] - 'a' == prevCh) {
            ans = 0;
        }
        else {
            ans = dp(idx+1, s[idx]-'a', s);
        }
    }
    ans %= mod;
    return mem[idx][prevCh] = ans;
}

long long getCount(string s) {
    int n = s.size();

    long long ans = 0;
    memset(mem, -1, sizeof(mem));
    if(s[0] == '?' and s[n-1] == '?') {
        for(int ch = 0; ch < 26; ch++) {
            firstCh = ch;
            memset(mem, -1, sizeof(mem));
            ans += dp(1, firstCh, s);
        }
    }
    else if(s[0] == '?' and s[n-1] != '?') {
        firstCh = s[n-1] - 'a';
        ans += dp(1, firstCh, s);
    }
    else if(s[0] != '?' and s[n-1] == '?') {
        firstCh = s[0] - 'a';
        ans += dp(1, firstCh, s);
    }
    else {
        if(s[0] != s[n-1]) {
            return 0;
        }
        firstCh = s[0] - 'a';
        ans += dp(1, firstCh, s);
    }
    return ans;
}