2022-06-17

LeetCode 括号问题详解

如果经常刷LeetCode的话，其实应该会对有一道题目印象非常深刻。那就是括号问题 [20] Valid Parentheses 。第一次看到这道题的话多少都会楞一下，因为乍一看题目内容非常的简单，无非是判断括号闭合的合法与否，但是仔细想想其实也有不少坑。尽管这道题是LeetCode中序号最小的堆栈问题，但是第一次做不一定能反应过来是堆栈。

这类题在LeetCode中一共有三道。分别是：

[20] Valid Parentheses Easy
[921] Minimum Add to Make Parentheses Valid Medium
[1541] Minimum Insertions to Balance a Parentheses String Medium

但是很离谱的是，我个人做下来的感觉 [20] Valid Parentheses 才是Medium的难度，剩下两道毫无疑问是Easy难度的，甚至它们因为太简单可能做的时候不一定能直观感受到堆栈的思想。当然，后两题如果追求极限的低复杂度（比如O(1)）的话，还是很有挑战的。

还是来聊聊这类题目的基本思路吧，这里先以 [20] Valid Parentheses 为例。其实基本思路不复杂，如果你理解堆栈的概念，其实一瞬间就能想明白是怎么一回事情。

+────+────+────+────+────+────+
| {  | [  | (  | (  | [  | (  |  <-- ')' Accept
+────+────+────+────+────+────+
|   +────+────+────+────+────+────+
--> | {  | [  | (  | (  | [  | X  |  <-- '('&')' Clear
    +────+────+────+────+────+────+
+────+────+────+────+────+────+
| {  | [  | (  | (  | [  | (  |  <-- ']' Dismatch
+────+────+────+────+────+────+

从上图可以看到对于每一个左括号，我们都按照顺序（先进后出，后进先出）放入堆栈中。但是对于右括号，我们要做的是两个核心步骤：

将其和堆栈最上层的那个左括号进行对比，如果成对，则安全匹配。
完成匹配后，将这个最上层的左括号消掉。然后如此循环往复，如果能够消除干净，则字符串Syntax合法。

从上面两个步骤又可以分别写出两个对应的逻辑，对于步骤一，所谓的对比就是对右括号本身取对应的左括号：

char left(char c) {
    if (c == 41) {return 40;}
    else if (c == 93) {return 91;}
    else {return 123;}
}

对于步骤二，只需要对整个输入的字符串进行逐字对比，并不停调用步骤一的left(char c)。

for (int i = 0; i < len; ++i) {
    if (s[i] == 40 || s[i] == 91 || s[i] == 123) {++idx; status[idx] = s[i];}
    else {
        if (left(s[i]) == status[idx]) {--idx;}
        else {return false;}
    }
}

将两个函数进行拼合，并对边界情况进行处理之后，便是 [20] Valid Parentheses 的答案了（个人习惯用数字替代ascii码的对比）：

char left(char c) {
    if (c == 41) {return 40;}
    else if (c == 93) {return 91;}
    else {return 123;}
}

bool isValid(char * s){
    int len=strlen(s);
    if (len == 1) {return false;}
    int *status = (int *)malloc(sizeof(int) * 10001);
    memset(status, 0, 10001);
    int idx = 0;

    for (int i = 0; i < len; ++i) {
        if (s[i] == 40 || s[i] == 91 || s[i] == 123) {++idx; status[idx] = s[i];}
        else {
            if (left(s[i]) == status[idx]) {--idx;}
            else {return false;}
        }
    }
    bool res;
    return res = (idx == 0) ? true : false;
}

其实这类括号题目，最重要就是第一时间要意识到是堆栈的思路，其次是需要对括号字符串有取左或者取右的直觉。这样其实就可以超快速解题了。

下面来看看另外两道标注了Medium，实则更简单的括号类问题。

先以 [921] Minimum Add to Make Parentheses Valid 为例，这道题真的不知道是怎么被评定为Medium的，其实这里本质就两种情况：入栈的是左括号 & 入栈的是右括号。对于入栈的是左括号的情况，用一个状态变量status记录一下还欠缺右括号的数量。对于入栈的是右括号，如果左括号还有结余，也就是status > 0，直接进行堆栈抵消；对于左括号没有结余的情况，就必须让左括号进行增补，也就是++res;。事实上这已经是一个一维堆栈了，而 [20] Valid Parentheses 至少还是一个二维堆栈。

int minAddToMakeValid(char * s){
    int len = strlen(s), status = 0, res = 0;
    for (int i = 0; i < len; ++i)
    {
        if (s[i] == 40) {++status;}
        else {
            if (status > 0) {--status;}
            else {++res;}
        }
    } 
    return res + status;
}

接下来我们再来聊聊 [1541] Minimum Insertions to Balance a Parentheses String。这道题完完全全就是 [921] Minimum Add to Make Parentheses Valid 的轻度升级版。唯一区别是把 ( & ) 的括号对异化为了 ( & )) 。这就意味着我们需要多做一件事情：把字符串先还原为Q921中的字符串，然后执行Q921的解法即可。这真的称不上是Medium难度。

需要新增的格式化步骤如下，主要是增加了对于单个右括号的增补处理，需要注意单个右括号在字符串最末尾的特殊情况：

for (int i=0,j=0; i < len; ++i, ++j) {
    if (s[i] == 40) {new[j] = s[i];}
    else {
        if (i != len - 1 && s[i + 1] == 41) {new[j] = ')'; ++i;} 
        else {new[j] = ')'; ++res;}
    }
}

然后把格式化步骤和 [921] 的答案结合一下，即为 [1541] 的正确解法：

int minInsertions(char * s){
    int res = 0,len = strlen(s);
    char *new = (char *)malloc(sizeof(char) * 3 * len);
    memset(new, '\0', 3*len);

    for (int i=0,j=0; i < len; ++i, ++j) {
        if (s[i] == 40) {new[j] = s[i];}
        else {
            if (i != len - 1 && s[i + 1] == 41) {new[j] = ')'; ++i;} 
            else {new[j] = ')'; ++res;}
        }
    }
    int i = 0, status = 0;
    while (new[i] != '\0')
    {
        if (new[i] == 40) {++status;}
        else {
            if (status > 0) {--status;}
            else {++res;}
        }
        ++i;
    }
    
    return res + status*2;
}

总结： 这类括号问题的关键是什么相信也比较明了了，其实就是堆栈思路。无论是 [20] 的二维堆栈，还是后面两道题目的一维堆栈，其实本质是一样的。而难度本身也至多围绕其他方面展开，比如增加字符串预处理之类的。不过还是有点期待会不会在未来出现三维的堆栈。

Kivinsae's Nest

化繁为简

LeetCode 括号问题详解