algoadvance

Leetcode 1678. Goal Parser Interpretation

Problem Statement

You are given a string command that represents the instructions for a Goal Parser. The Goal Parser interprets the string command as follows:

You need to return the interpreted string.

Example:

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

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

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

Clarifying Questions

  1. Q: Are there any restrictions on the length of the input string command? A: The problem does not specify a restriction, but typically strings in such problems are not excessively long.

  2. Q: Can the input string contain characters other than “G”, “(“, “)”, and “al”? A: No, the input string command will be composed only of these characters in the specified patterns.

  3. Q: Is the input string guaranteed to be a valid command string according to the described rules? A: Yes, it’s safe to assume the input string is valid based on the problem description.

Strategy

Given that we need to replace specific patterns in the string, we can use a string builder to accumulate the interpreted command:

  1. Initialize an empty StringBuilder to build the interpreted command.
  2. Traverse the command string character by character.
  3. If the current character is 'G', append 'G' to the builder.
  4. If the current character is '(':
    • If the next character is ')', append 'o' and move the pointer two steps ahead.
    • If the next two characters are 'a' and 'l', append 'al' and move the pointer four steps ahead.
  5. Return the constructed interpreted command from the StringBuilder.

Code

public class GoalParser {
    public String interpret(String command) {
        StringBuilder result = new StringBuilder();
        int i = 0;
        while (i < command.length()) {
            if (command.charAt(i) == 'G') {
                result.append('G');
                i++;
            } else if (command.charAt(i) == '(') {
                // Check for "()"
                if (command.charAt(i + 1) == ')') {
                    result.append('o');
                    i += 2;
                } else {
                    // It must be "(al)"
                    result.append("al");
                    i += 4;
                }
            }
        }
        return result.toString();
    }

    public static void main(String[] args) {
        GoalParser parser = new GoalParser();
        System.out.println(parser.interpret("G()(al)"));         // Output: "Goal"
        System.out.println(parser.interpret("G()()()()(al)"));   // Output: "Gooooal"
        System.out.println(parser.interpret("(al)G(al)()()G"));  // Output: "alGalooG"
    }
}

Time Complexity

This approach efficiently interprets the Goal Parser’s command string by examining each character only once, resulting in optimal time complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI