(标签-c++|关键词-括号匹配)

Question

给定
T 个仅包含大写字母 A，B，C 的字符串
s。问你是否能够通过将每个 A，B，C 换成 (，) 中的一个（同一个字母必须要换成同一个字符），使得最后得到的括号序列能够完全匹配。括号匹配函数c++代码

Answer 1

引自免费微信小程序：皆我百晓生

这个问题可以通过回溯算法来解决，我们首先遍历所有可能的替换操作，并检查这些操作是否会导致括号匹配。这里是一个简单的实现方法。

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    bool canBeValid(string s) {
        // 遍历所有的A, B, C
        for (int i = 0; i < s.size(); ++i) {
            char c = s[i];
            if (c == 'A') { // 如果是A
                // 确保有下一个字符并且是B
                if (i + 1 < s.size() && s[i+1] == 'B')
                    i++; // 移动到下一个字符
                else return false; // 如果没有B，则无法匹配
            } else if (c == 'B') { // 如果是B
                // 确保有下一个字符并且是C
                if (i + 1 < s.size() && s[i+1] == 'C')
                    i += 2; // 移动到下一个字符并添加一个()
                else return false; // 如果没有C，则无法匹配
            } else if (c == 'C') { // 如果是C
                // 确保有下一个字符并且是A
                if (i + 1 < s.size() && s[i+1] == 'A')
                    i += 2; // 移动到下一个字符并添加一个(
                else return false; // 如果没有A，则无法匹配
            }
        }
        return true;
    }
};

int main() {
    Solution solution;
    string test_string = "ABC";
    cout << (solution.canBeValid(test_string) ? "True" : "False") << endl;
    return 0;
}

这段代码会遍历输入的字符串，对于每一个字母，它会确保后面至少有一个匹配的字母。如果在某个位置找不到匹配的字母，则返回false，表示当前的字符串不能进行有效的括号匹配。