题目描述
请你设计一个可以解释字符串 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
(模拟) $O(n)$
从前往后遍历每个字符,并判断以该字符为开头的子串是G
,()
或(al)
中的哪一个进行替换即可
时间复杂度
遍历字符需要$O(n)$的时间,由于模式串很短,因此每次判断可以看做$O(1)$的时间,故总时间复杂度为$O(n)$
C++ 代码
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';
}else if(command[i] == '('){
if(command[i + 1] == ')') {
ans += 'o';
i++;
}else{
ans += "al";
i += 3;
}
}
}
return ans;
}
};