力扣(LeetCode)1678. 设计 Goal 解析器(C++)

栈模拟

栈模拟 : 遍历 $command$ 的所有字符，记作 $x$ 。 $x$ 是 ${}^{\prime }{G}^{\prime }$ , $ans+={}^{\prime }{G}^{\prime }$ 。 $x$ 不是 ${}^{\prime }{)}^{\prime }$ 则压栈 $x$ ； $x$ 是 ${}^{\prime }{)}^{\prime }$ , 则匹配栈顶的字符，匹配一个字符，弹栈一个，遇到 ${}^{\prime }{a}^{\prime }$ ，$cntA$++，直到栈顶为 ${}^{\prime }{(}^{\prime }$ 停止匹配。如果 $cntA$ 为 $0$ ，$ans+={}^{\prime }{o}^{\prime }$ ，否则 $ans+={}^{\prime }a{l}^{\prime }$。

考虑到昨天的打卡题，一时手痒，想用栈来做今天的题。当然这题直接匹配也很简单，思路和栈模拟大致相似。

代码展示

直接匹配

class Solution {
public:
    string interpret(string command) {
        string ans="";
        int cntA=0;
        for(auto x:command){
            if('a'==x) cntA++;
            else if(')'==x){
                if(cntA){
                    ans+="al";
                    cntA=0;
                }
                else ans+='o';
            }
            else if('G'==x) ans+=x;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

栈模拟

class Solution {
public:
    string interpret(string command) {
        stack <char> stk;
        //遇到G,ans+=G;遇到)，统计当前匹配，其他字符压栈。
        string ans="";
        for(auto x:command){
            int cntA = 0;
            if('G'==x) ans +=x;
            else if(')'==x) {//遇到')'弹栈匹配
                if(stk.top()=='l') stk.pop();
                if(stk.top()=='a'){
                    stk.pop();
                    cntA++;
                }
                if(stk.top()=='('){
                    stk.pop();//弹出'('
                    if(cntA) ans+="al";
                    else ans+="o";
                }
            }
            else stk.push(x);//其他字符
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

栈模拟复杂度分析

1. 时间复杂度:$O(n)$， $n$ 是 $command$ 的长度。一次遍历 $expression$ 的时间复杂度是$O(n)$。
2. 空间复杂度:$O(n)$。字符栈 $stk$ 最多压栈 $n$ 个元素，最坏空间复杂度 $O(n)$。

直接匹配复杂度分析

1. 时间复杂度:$O(n)$， 一次遍历 $expression$ 的时间复杂度是$O(n)$。
2. 空间复杂度:$O(1)$，除若干变量使用的常量级空间，没有使用额外的线性空间。