LeetCode-1678. 设计 Goal 解析器【字符串】

题目描述：

请你设计一个可以解释字符串 command 的 Goal 解析器 。command 由 “G”、“()” 和/或 “(al)” 按某种顺序组成。Goal 解析器会将 “G” 解释为字符串 “G”、“()” 解释为字符串 “o” ，“(al)” 解释为字符串 “al” 。然后，按原顺序将经解释得到的字符串连接成一个字符串。

给你字符串 command ，返回 Goal 解析器 对 command 的解释结果。

示例 1：

输入：command = “G()(al)”
输出：“Goal”
解释：Goal 解析器解释命令的步骤如下所示：
G -> G
() -> o
(al) -> al
最后连接得到的结果是 “Goal”

示例 2：

输入：command = “G()()()()(al)”
输出：“Gooooal”
示例 3：

输入：command = “(al)G(al)()()G”
输出：“alGalooG”

提示：

1 <= command.length <= 100
command 由 “G”、“()” 和/或 “(al)” 按某种顺序组成
https://leetcode.cn/problems/goal-parser-interpretation/description/

解题思路一：跳过部分遍历，偷鸡方法。

首先将command分为两种类型1.‘G’；2.‘(’。当遇到’G’时直接加入ans，遇到’(‘时判断command[i+1]如果是’)'将’o’加入ans且++i。否则将’al’入栈且i+=3。

class Solution {
public:
    string interpret(string command) {
        string ans="";
        int n=command.size();
        for(int i=0;i<n;++i){
            if(command[i]=='G') ans+='G';//首先将command分为两种类型1.'G'；2.'('。当遇到'G'时直接加入ans
            else{//遇到'('时判断command[i+1]如果是')'将'o'加入ans且++i。
                if(command[i+1]==')'){
                    ans+='o';++i;
                }else{//否则将'al'入栈且i+=3。
                    ans+="al";i+=3;
                }
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度：O(n)
空间复杂度：O(1)ans作为返回值不算

解题思路二：字符串替换stl，只需要将字符串 command 中的 “()” 替换为 ‘o’，“(al)” 替换为 “al” 即可。

class Solution {
public:
    string interpret(string command) {
        while(command.find("()")!=-1) command.replace(command.find("()"),2,"o");
        while(command.find("(al)")!=-1) command.replace(command.find("(al)"),4,"al");
        return command;
    }
};
1
2
3
4
5
6
7
8

时间复杂度较高

解题思路三：0

1