字符串题目:设计 Goal 解析器

wuchangjian2021-11-04 18:00:43编程学习

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:设计 Goal 解析器

出处:1678. 设计 Goal 解析器

难度

2 级

题目描述

要求

请你设计一个可以解释字符串 command \texttt{command} commandGoal 解析器 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} 1command.length100
  • 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

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。