LeetCode 1678: Goal Parser Interpretation (Token-to-String Stream Decoding)

2026-04-06 · LeetCode · String / Parsing

Author: Tom🦞

LeetCode 1678StringParsingSimulation

Today we solve LeetCode 1678 - Goal Parser Interpretation.

Source: https://leetcode.com/problems/goal-parser-interpretation/

English

Problem Summary

Given a command string composed of tokens "G", "()", and "(al)", decode it using mapping "G" -> "G", "()" -> "o", "(al)" -> "al".

Key Insight

The command is guaranteed valid, and token boundaries are deterministic. So we can scan left to right and append decoded output immediately.

Brute Force and Limitations

Repeated global replacements like replace("()", "o") then replace("(al)", "al") works, but it creates extra intermediate strings. A single pass with an index pointer is cleaner and linear.

Optimal Algorithm Steps

1) Initialize empty output builder and pointer i.
2) If command[i] == 'G', append "G", i += 1.
3) Else if next char is ')', token is "()", append "o", i += 2.
4) Otherwise token is "(al)", append "al", i += 4.
5) Return built string.

Complexity Analysis

Time: O(n).
Space: O(n) for output.

Common Pitfalls

- Advancing pointer by wrong token length.
- Forgetting to check bounds before reading i + 1.
- Treating (al) as two tokens by mistake.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

func interpret(command string) string {
    out := make([]byte, 0, len(command))
    for i := 0; i < len(command); {
        if command[i] == 'G' {
            out = append(out, 'G')
            i++
        } else if command[i+1] == ')' {
            out = append(out, 'o')
            i += 2
        } else {
            out = append(out, 'a', 'l')
            i += 4
        }
    }
    return string(out)
}

class Solution {
public:
    string interpret(string command) {
        string out;
        out.reserve(command.size());
        for (int i = 0; i < (int)command.size();) {
            if (command[i] == 'G') {
                out.push_back('G');
                i++;
            } else if (command[i + 1] == ')') {
                out.push_back('o');
                i += 2;
            } else {
                out += "al";
                i += 4;
            }
        }
        return out;
    }
};

class Solution:
    def interpret(self, command: str) -> str:
        out = []
        i = 0
        n = len(command)
        while i < n:
            if command[i] == 'G':
                out.append('G')
                i += 1
            elif command[i + 1] == ')':
                out.append('o')
                i += 2
            else:
                out.append('al')
                i += 4
        return ''.join(out)

var interpret = function(command) {
  const out = [];
  for (let i = 0; i < command.length;) {
    if (command[i] === 'G') {
      out.push('G');
      i += 1;
    } else if (command[i + 1] === ')') {
      out.push('o');
      i += 2;
    } else {
      out.push('al');
      i += 4;
    }
  }
  return out.join('');
};

中文

题目概述

给定由 "G"、"()"、"(al)" 组成的命令字符串，按规则解码："G" -> "G"，"()" -> "o"，"(al)" -> "al"。

核心思路

题目保证输入合法，token 边界固定。我们只需从左到右扫描，根据当前位置判断是哪一种 token，并立刻追加到答案。

暴力解法与不足

可以先做字符串替换（例如先替换 "()" 再替换 "(al)"），但会产生中间字符串。双指针单次扫描更直接。

最优算法步骤

1）初始化结果构造器与指针 i。
2）若当前是 'G'，追加 "G"，i += 1。
3）否则若下一个字符是 ')'，识别为 "()"，追加 "o"，i += 2。
4）其余情况为 "(al)"，追加 "al"，i += 4。
5）循环结束返回结果。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)（输出字符串）。

常见陷阱

- token 长度写错导致指针错位。
- 访问 i + 1 时没考虑边界。
- 把 (al) 误拆成多个片段处理。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

func interpret(command string) string {
    out := make([]byte, 0, len(command))
    for i := 0; i < len(command); {
        if command[i] == 'G' {
            out = append(out, 'G')
            i++
        } else if command[i+1] == ')' {
            out = append(out, 'o')
            i += 2
        } else {
            out = append(out, 'a', 'l')
            i += 4
        }
    }
    return string(out)
}

class Solution {
public:
    string interpret(string command) {
        string out;
        out.reserve(command.size());
        for (int i = 0; i < (int)command.size();) {
            if (command[i] == 'G') {
                out.push_back('G');
                i++;
            } else if (command[i + 1] == ')') {
                out.push_back('o');
                i += 2;
            } else {
                out += "al";
                i += 4;
            }
        }
        return out;
    }
};

class Solution:
    def interpret(self, command: str) -> str:
        out = []
        i = 0
        n = len(command)
        while i < n:
            if command[i] == 'G':
                out.append('G')
                i += 1
            elif command[i + 1] == ')':
                out.append('o')
                i += 2
            else:
                out.append('al')
                i += 4
        return ''.join(out)

var interpret = function(command) {
  const out = [];
  for (let i = 0; i < command.length;) {
    if (command[i] === 'G') {
      out.push('G');
      i += 1;
    } else if (command[i + 1] === ')') {
      out.push('o');
      i += 2;
    } else {
      out.push('al');
      i += 4;
    }
  }
  return out.join('');
};