题目

标题和出处

标题：设计 Goal 解析器

出处：1678. 设计 Goal 解析器

难度

2 级

题目描述

要求

请你设计一个可以解释字符串 的 Goal 解析器。 由 、%22%7D#card=math&code=%5Ctexttt%7B%22%28%29%22%7D&id=BpeXS) 和/或 %22%7D#card=math&code=%5Ctexttt%7B%22%28al%29%22%7D&id=dZ4qi) 按某种顺序组成。Goal 解析器会将 解释为字符串 ，%22%7D#card=math&code=%5Ctexttt%7B%22%28%29%22%7D&id=LbKGn) 解释为字符串 ，%22%7D#card=math&code=%5Ctexttt%7B%22%28al%29%22%7D&id=JehtZ) 解释为字符串 。然后，按原顺序将经解释得到的字符串连接成一个字符串。

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

示例

示例 1：

输入：(al)%22%7D#card=math&code=%5Ctexttt%7Bcommand%20%3D%20%22G%28%29%28al%29%22%7D&id=NqahZ)
输出：
解释：Goal 解析器解释命令的步骤如下所示：

%20-%3E%20o%7D#card=math&code=%5Ctexttt%7B%28%29%20-%3E%20o%7D&id=uOgyV)
%20-%3E%20al%7D#card=math&code=%5Ctexttt%7B%28al%29%20-%3E%20al%7D&id=XmG55)
最后连接得到的结果是

示例 2：

输入：()()()(al)%22%7D#card=math&code=%5Ctexttt%7Bcommand%20%3D%20%22G%28%29%28%29%28%29%28%29%28al%29%22%7D&id=Op51k)
输出：

示例 3：

输入：G(al)()()G%22%7D#card=math&code=%5Ctexttt%7Bcommand%20%3D%20%22%28al%29G%28al%29%28%29%28%29G%22%7D&id=X65Ql)
输出：

数据范围

• 
• 由 、%22%7D#card=math&code=%5Ctexttt%7B%22%28%29%22%7D&id=vXPfV) 和/或 %22%7D#card=math&code=%5Ctexttt%7B%22%28al%29%22%7D&id=oGNrP) 按某种顺序组成

解法

思路和算法

由于给定的字符串 由 、 和/或 按某种顺序组成，因此一定可以正确地解析字符串 ，不需要考虑不合法的情况。

从左到右遍历字符串 ，使用 类型的变量存储解析之后的结果。具体而言，根据当前字符和下一个字符决定当前需要解析的字符个数。

• 如果当前字符是 ，则当前需要解析 个字符，解析结果是 ；
• 如果当前字符是 ，则根据下一个字符解析：
  • 如果下一个字符是 ，则当前需要解析 个字符，解析结果是 ；
  • 如果下一个字符不是 ，则当前需要解析 个字符，解析结果是 。

遍历过程中维护下标值。每次将下标处的字符作为当前字符，解析之后，将下标值更新，继续对剩下部分解析。当下标值超出字符串的下标范围时，解析结束。

代码

class Solution {
    public String interpret(String command) {
        int length = command.length();
        StringBuffer sb = new StringBuffer();
        int index = 0;
        while (index < length) {
            char c = command.charAt(index);
            if (c == 'G') {
                sb.append("G");
                index++;
            } else {
                if (command.charAt(index + 1) == ')') {
                    sb.append("o");
                    index += 2;
                } else {
                    sb.append("al");
                    index += 4;
                }
            }
        }
        return sb.toString();
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28n%29&id=RlD6V)，其中 是字符串 的长度。需要遍历字符串一次。
• 空间复杂度：#card=math&code=O%28n%29&id=KoRRj)，其中 是字符串 的长度。需要创建一个 类型的变量存储解析后的结果，长度不会超过 。