文章目录
题目
标题和出处
标题：设计 Goal 解析器
难度
2 级
题目描述
要求
请你设计一个可以解释字符串 command \texttt{command} command 的 Goal 解析器。 command \texttt{command} command 由 "G" \texttt{"G"} "G"、 "()" \texttt{"()"} "()" 和/或 "(al)" \texttt{"(al)"} "(al)" 按某种顺序组成。Goal 解析器会将 "G" \texttt{"G"} "G" 解释为字符串 "G" \texttt{"G"} "G"， "()" \texttt{"()"} "()" 解释为字符串 "o" \texttt{"o"} "o"， "(al)" \texttt{"(al)"} "(al)" 解释为字符串 "al" \texttt{"al"} "al"。然后，按原顺序将经解释得到的字符串连接成一个字符串。
给你字符串 command \texttt{command} command，返回 Goal 解析器 对 command \texttt{command} command 的解释结果。
示例
示例 1：
输入：
command
=
"G()(al)"
\texttt{command = "G()(al)"}
command = "G()(al)"
输出：
"Goal"
\texttt{"Goal"}
"Goal"
解释：Goal 解析器解释命令的步骤如下所示：
G
->
G
\texttt{G -> G}
G -> G
()
->
o
\texttt{() -> o}
() -> o
(al)
->
al
\texttt{(al) -> al}
(al) -> al
最后连接得到的结果是
"Goal"
\texttt{"Goal"}
"Goal"
示例 2：
输入：
command
=
"G()()()()(al)"
\texttt{command = "G()()()()(al)"}
command = "G()()()()(al)"
输出：
"Gooooal"
\texttt{"Gooooal"}
"Gooooal"
示例 3：
输入：
command
=
"(al)G(al)()()G"
\texttt{command = "(al)G(al)()()G"}
command = "(al)G(al)()()G"
输出：
"alGalooG"
\texttt{"alGalooG"}
"alGalooG"
数据范围
- 1 ≤ command.length ≤ 100 \texttt{1} \le \texttt{command.length} \le \texttt{100} 1≤command.length≤100
- command \texttt{command} command 由 "G" \texttt{"G"} "G"、 "()" \texttt{"()"} "()" 和/或 "(al)" \texttt{"(al)"} "(al)" 按某种顺序组成
解法
思路和算法
由于给定的字符串 command \textit{command} command 由 “G" \text{``G"} “G"、 “()" \text{``()"} “()" 和/或 “(al)" \text{``(al)"} “(al)" 按某种顺序组成，因此一定可以正确地解析字符串 command \textit{command} command，不需要考虑不合法的情况。
从左到右遍历字符串 command \textit{command} command，使用 StringBuffer \texttt{StringBuffer} StringBuffer 类型的变量存储解析之后的结果。具体而言，根据当前字符和下一个字符决定当前需要解析的字符个数。
-
如果当前字符是 ‘G’ \text{`G'} ‘G’，则当前需要解析 1 1 1 个字符，解析结果是 “G" \text{``G"} “G"；
-
如果当前字符是 ‘(’ \text{`('} ‘(’，则根据下一个字符解析：
-
如果下一个字符是 ‘)’ \text{`)'} ‘)’，则当前需要解析 2 2 2 个字符，解析结果是 “o" \text{``o"} “o"；
-
如果下一个字符不是 ‘)’ \text{`)'} ‘)’，则当前需要解析 4 4 4 个字符，解析结果是 “al" \text{``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 \textit{command} command 的长度。需要遍历字符串一次。
-
空间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 command \textit{command} command 的长度。需要创建一个 StringBuffer \texttt{StringBuffer} StringBuffer 类型的变量存储解析后的结果，长度不会超过 n n n。