# Goal Parser Interpretation
**Difficulty:** EASY
[External](https://leetcode.com/problems/goal-parser-interpretation)
Canonical: https://scaleengineer.com/dsa/problems/goal-parser-interpretation
**Data structures:** String
---
## Problem
You own a **Goal Parser** that can interpret a string `command`. The `command` consists of an alphabet of `"G"`, `"()"` and/or `"(al)"` in some order. 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`.

**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` consists of `"G"`, `"()"`, and/or `"(al)"` in some order.

# Approaches
## Using String replace()
This approach leverages the built-in `replace()` method of the String class. It's a very direct and high-level way to solve the problem. We simply replace all occurrences of `"()"` with `"o"` and then all occurrences of `"(al)"` with `"al"`.
**Time:** O(N), where N is the length of the command string. Although `replace()` is called twice, each call scans the string. In Java, `String.replace()` creates a new string, so the total time is proportional to the length of the string for each operation, resulting in a linear time complexity. · **Space:** O(N), where N is the length of the command string. This is because strings in Java are immutable. Each call to `replace()` can potentially create a new string of length up to N, leading to space usage for the intermediate and final strings.
**Pros:** Extremely simple and concise to write.; Highly readable and easy to understand for other developers.
**Cons:** Creates intermediate string objects, which can be inefficient in terms of memory and performance, especially for very large input strings.; Involves multiple passes over the string data, making it theoretically slower than a single-pass solution.
### Explanation
This method is the most straightforward due to its use of high-level string manipulation functions. The logic is simple: perform a series of replacements on the original string until all special sequences are converted to their interpretations. While easy to write, it's not the most performant solution because string immutability in Java means each replacement operation creates a new string in memory.

```java
class Solution {
    public String interpret(String command) {
        // First, replace all occurrences of "()" with "o"
        String result = command.replace("()", "o");
        // Then, replace all occurrences of "(al)" with "al"
        result = result.replace("(al)", "al");
        return result;
    }
}
```
### Algorithm
- 1. Take the input `command` string.
- 2. Use the `String.replace()` method to substitute all occurrences of `"()"` with `"o"`. This creates a new intermediate string.
- 3. On the intermediate string, use the `String.replace()` method again to substitute all occurrences of `"(al)"` with `"al"`.
- 4. Return the final resulting string.

## Single Pass with StringBuilder
A more optimal approach is to iterate through the input string just once and build the result string using a `StringBuilder`. This avoids the overhead of creating multiple intermediate string objects that the `replace()` method incurs, making it more efficient in both time and memory.
**Time:** O(N), where N is the length of the command string. We iterate through the string a single time. Appending to a `StringBuilder` is an amortized O(1) operation. · **Space:** O(N), where N is the length of the command string. The `StringBuilder` can grow up to the size of the input string in the worst case (e.g., a command of all 'G's).
**Pros:** More efficient in terms of both time and memory as it avoids creating intermediate strings.; Processes the input in a single pass, which is optimal.
**Cons:** The code is slightly more verbose and requires manual index management compared to the `replace()` method.
### Explanation
By iterating through the string character by character, we can make decisions based on the current and upcoming characters to parse the command. We use a `StringBuilder` because it is a mutable sequence of characters, allowing for efficient appends without creating a new object for each addition. This single-pass approach is generally preferred for string manipulation tasks where performance is a consideration.

```java
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 (c == '(') {
                // Check the next character to distinguish between "()" and "(al)"
                if (command.charAt(i + 1) == ')') {
                    sb.append('o');
                    i += 2; // Skip over '()'
                } else {
                    sb.append("al");
                    i += 4; // Skip over '(al)'
                }
            }
        }
        return sb.toString();
    }
}
```
### Algorithm
- 1. Initialize an empty `StringBuilder` to store the result.
- 2. Iterate through the `command` string using an index `i` from `0` to `length - 1`.
- 3. At each character `command.charAt(i)`:
  - If the character is `'G'`, append `'G'` to the `StringBuilder` and increment `i` by 1.
  - If the character is `'('`:
    - Check the next character at `i + 1`.
    - If `command.charAt(i + 1)` is `')'`, it signifies a `"()"` token. Append `'o'` to the `StringBuilder` and advance the index `i` by 2.
    - Otherwise, it must be an `"(al)"` token. Append `"al"` to the `StringBuilder` and advance the index `i` by 4.
- 4. After the loop completes, convert the `StringBuilder` to a string and return it.

# Solutions
### Java

```java
class Solution { public String interpret ( String command ) { return command . replace ( "()" , "o" ). replace ( "(al)" , "al" ); } }
```

### CPP

```cpp
class Solution { public: string interpret ( string command ) { while ( command . find ( "()" ) != - 1 ) command . replace ( command . find ( "()" ), 2 , "o" ); while ( command . find ( "(al)" ) != - 1 ) command . replace ( command . find ( "(al)" ), 4 , "al" ); return command ; } };
```

### Python

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