Goal Parser Interpretation

Difficulty: Easy | Acceptance: 88.10% | Paid: No Topics: String

You own a Goal Parser that can interpret a string command. The command consists of an alphabet of “G”, ”()”, and “(al)“. The Goal Parser will interpret “G” as the string “G”, ”()” as the string “o”, and “(al)” as the string “al”. The interpreted strings are then concatenated in the original order.

Given the string command, return the Goal Parser’s interpretation of command.

• Examples
• Constraints
• Built-in String Replacement
• Iterative Parsing
• Regular Expressions

Examples

Example 1:

Input: command = "G()(al)"
Output: "Goal"
Explanation: The Goal Parser interprets the command as follows:
G -> G
() -> o
(al) -> al
The final concatenated result is "Goal".

Example 2:

Input: command = "G()()()()(al)"
Output: "Gooooal"

Example 3:

Input: command = "(al)G(al)()()G"
Output: "alGalooG"

Constraints

1 <= command.length <= 100
command[i] is one of 'G', '(', ')', 'a', 'l'.

Built-in String Replacement

Intuition The problem requires mapping specific substrings to other strings. Since the mappings are distinct and fixed, we can directly use the string replacement functions provided by standard libraries to transform the input string into the output.

Steps

• First, replace all occurrences of “(al)” with “al”. This must be done first to avoid partial matches with ”()“.
• Next, replace all occurrences of ”()” with “o”.
• The character “G” remains unchanged, so no replacement is needed for it.
• Return the modified string.

class Solution:
    def interpret(self, command: str) -> str:
        return command.replace("(al)", "al").replace("()", "o")

Complexity

• Time: O(n) - String replacement typically scans the string.
• Space: O(n) - To store the new string.
• Notes: Very concise and readable. The order of replacement is critical.

Iterative Parsing

Intuition We can scan the string character by character. If we encounter a ‘G’, we add it to the result. If we encounter an ’(’, we look ahead to determine if it forms ”()” or “(al)” and append the corresponding result.

Steps

• Initialize an empty result list/string builder and an index i at 0.
• Loop while i is less than the length of the command.
• If the character at i is ‘G’, append ‘G’ to the result and increment i.
• If the character at i is ’(’, check the character at i + 1.
  • If it is ’)’, append ‘o’ to the result and increment i by 2.
  • If it is ‘a’, append ‘al’ to the result and increment i by 4 (to skip past “(al)”).
• Return the joined result string.

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

Complexity

• Time: O(n) - We visit each character at most once.
• Space: O(n) - To store the result.
• Notes: Efficient single-pass algorithm.

Regular Expressions

Intuition We can use a regular expression to match all valid tokens (“G”, ”()”, or “(al)”) simultaneously and replace them with their corresponding interpretations using a mapping function or replacement string.

Steps

• Define a regex pattern that matches “G”, ”()”, or “(al)“.
• Use the language’s regex replace function with a callback/mapping to transform matches:
  • “G” -> “G"
  • "()” -> “o"
  • "(al)” -> “al”
• Return the result.

import re

class Solution:
    def interpret(self, command: str) -> str:
        def repl(match):
            if match.group() == '()': return 'o'
            if match.group() == '(al)': return 'al'
            return 'G'
        return re.sub(r'G|\(\)|\(al\)', repl, command)

Complexity

• Time: O(n) - Regex engines generally operate in linear time for simple patterns.
• Space: O(n) - For the result string.
• Notes: Flexible and powerful, but might be overkill for such simple fixed mappings.