判断字符串是否符合规则

概述

给定一个字符串，判断其是否符合一下三个规则之一：

1. 如果是空串则符合
2. 如果是 bSaSb，其中 S 是符合规则的字符串，则也符合
3. 如果是 cScS，其中 S 是符合规则的字符串，则也符合

递归法 + cache 法

因为我第一次写的时候就加了 cache，不知道不加会不会超时。

#include <bits/stdc++.h>
using namespace std;

unordered_map<string, int> dp;
bool isValid(string& s) {
    if (s.empty()) return true;
    if (dp.count(s)) return dp[s];
    bool res = false;
    int n = s.size();
    if (n % 2 == 0) {
        int i = 0, j = n / 2;
        if (s[i] == 'c' && s[j] == 'c') {
            string s1 = s.substr(i + 1, n / 2 - 1);
            string s2 = s.substr(j + 1, n / 2 - 1);
            if (s1 != s2) {
                res = false;
            } else {
                res = isValid(s1);
            }
        } else {
            res = false;
        }
    } else {
        if (s.front() == 'b' && s.back() == 'b' && s[n / 2] == 'a') {
            int l = (n - 3) / 2;
            string s1 = s.substr(1, l);
            string s2 = s.substr(n / 2 + 1, l);
            if (s1 != s2) {
                res = false;
            } else {
                res = isValid(s1);
            }
        } else {
            res = false;
        }
    }
    dp[s] = res;
    return res;
}

int main() {
    int T; cin >> T;
    for (int t = 0; t < T; t ++) {
        string s; cin >> s;
        if (isValid(s)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}

Links: 判断字符串是否符合规则

未经允许，禁止转载，本文源站链接：https://iamazing.cn/