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 _theGoal Parser ’s interpretation of _command.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2

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

Example 3

1
2

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

Constraints

  • 1 <= command.length <= 100
  • command consists of "G", "()", and/or "(al)" in some order.

Solution

Method 1 – String Replacement

Intuition

The problem is a simple string parsing task. We can directly replace the patterns “()” with “o” and “(al)” with “al” in the input string, as they do not overlap and are unique.

Approach

  1. Replace all occurrences of “(al)” with “al” in the input string.
  2. Replace all occurrences of “()” with “o” in the result.
  3. Return the final string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    string interpret(string command) {
        string ans;
        for (size_t i = 0; i < command.size(); ) {
            if (command[i] == 'G') {
                ans += 'G';
                i++;
            } else if (command.substr(i, 2) == "()") {
                ans += 'o';
                i += 2;
            } else if (command.substr(i, 4) == "(al)") {
                ans += "al";
                i += 4;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func interpret(command string) string {
    ans := ""
    for i := 0; i < len(command); {
        if command[i] == 'G' {
            ans += "G"
            i++
        } else if i+1 < len(command) && command[i:i+2] == "()" {
            ans += "o"
            i += 2
        } else if i+3 < len(command) && command[i:i+4] == "(al)" {
            ans += "al"
            i += 4
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public String interpret(String command) {
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < command.length(); ) {
            if (command.charAt(i) == 'G') {
                ans.append('G');
                i++;
            } else if (command.startsWith("()", i)) {
                ans.append('o');
                i += 2;
            } else if (command.startsWith("(al)", i)) {
                ans.append("al");
                i += 4;
            }
        }
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun interpret(command: String): String {
        val sb = StringBuilder()
        var i = 0
        while (i < command.length) {
            when {
                command[i] == 'G' -> {
                    sb.append('G')
                    i++
                }
                command.startsWith("()", i) -> {
                    sb.append('o')
                    i += 2
                }
                command.startsWith("(al)", i) -> {
                    sb.append("al")
                    i += 4
                }
            }
        }
        return sb.toString()
    }
}
1
2
3

class Solution:
    def interpret(self, command: str) -> str:
        return command.replace("(al)", "al").replace("()", "o")
1
2
3
4
5

impl Solution {
    pub fn interpret(command: String) -> String {
        command.replace("(al)", "al").replace("()", "o")
    }
}
1
2
3
4
5

class Solution {
    interpret(command: string): string {
        return command.replace(/\(al\)/g, "al").replace(/\(\)/g, "o");
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Each character is visited at most once.
  • 🧺 Space complexity: O(n) — Output string is proportional to input size.