题目

标题：设计 Goal 解析器

难度

2 级

题目描述

要求

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

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

示例

示例 1：

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

示例 2：

输入： command = "G()()()()(al)" exttt{command = "G()()()()(al)"} command = "G()()()()(al)" 输出： "Gooooal" exttt{"Gooooal"} "Gooooal"

示例 3：

输入： command = "(al)G(al)()()G" exttt{command = "(al)G(al)()()G"} command = "(al)G(al)()()G" 输出： "alGalooG" exttt{"alGalooG"} "alGalooG"

数据范围

1 ≤ command.length ≤ 100 exttt{1} le exttt{command.length} le exttt{100} 1≤command.length≤100 command exttt{command} command 由 "G" exttt{"G"} "G"、 "()" exttt{"()"} "()" 和/或 "(al)" exttt{"(al)"} "(al)" 按某种顺序组成

解法

思路和算法

由于给定的字符串 command extit{command} command 由 “G" ext{``G"} “G"、 “()" ext{``()"} “()" 和/或 “(al)" ext{``(al)"} “(al)" 按某种顺序组成，因此一定可以正确地解析字符串 command extit{command} command，不需要考虑不合法的情况。

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

如果当前字符是 ‘G’ ext{`G} ‘G’，则当前需要解析 1 1 1 个字符，解析结果是 “G" ext{``G"} “G"； 如果当前字符是 ‘(’ ext{`(} ‘(’，则根据下一个字符解析： 如果下一个字符是 ‘)’ ext{`)} ‘)’，则当前需要解析 2 2 2 个字符，解析结果是 “o" ext{``o"} “o"； 如果下一个字符不是 ‘)’ ext{`)} ‘)’，则当前需要解析 4 4 4 个字符，解析结果是 “al" ext{``al"} “al"。

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

代码

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();
    }
}

复杂度分析

时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 command extit{command} command 的长度。需要遍历字符串一次。 空间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 command extit{command} command 的长度。需要创建一个 StringBuffer exttt{StringBuffer} StringBuffer 类型的变量存储解析后的结果，长度不会超过 n n n。