algoadvance

Leetcode 1678. Goal Parser Interpretation

Problem Statement

You are given a string command that consists of “G”, “()” and/or “(al)” in some order. The goal is to interpret this string where:

Return the interpreted string.

Example 1:

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

Example 2:

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

Example 3:

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

Clarifying Questions

  1. What is the maximum length of the command string?
    • The constraints specify that the length of the command string will be between 1 and 100.
  2. Are there any invalid cases (e.g., strings that do not conform to the given patterns) we need to handle?
    • The constraint ensures the command string is always valid according to the provided patterns, so no need to handle invalid cases.
  3. Is the solution case-sensitive?
    • Yes, based on the examples, it is case-sensitive.

Strategy

  1. We will iterate through the command string.
  2. Whenever we encounter a ‘G’, we append ‘G’ to the result.
  3. If we encounter ‘()’, we append ‘o’ to the result.
  4. If we encounter ‘(al)’, we append ‘al’ to the result.
  5. We skip the appropriate number of characters after recognizing ‘()’, or ‘(al)’ to avoid reprocessing.

Time Complexity

Code

#include <iostream>
#include <string>

class Solution {
public:
    std::string interpret(std::string command) {
        std::string result;
        
        for (int i = 0; i < command.length(); ++i) {
            if (command[i] == 'G') {
                result += 'G';
            } else if (command[i] == '(' && command[i + 1] == ')') {
                result += 'o';
                i++; // Skip the next character
            } else if (command[i] == '(' && command[i + 1] == 'a') {
                result += "al";
                i += 3; // Skip the next three characters, i.e., "al)"
            }
        }
        
        return result;
    }
};

int main() {
    Solution solution;
    std::string command1 = "G()(al)";
    std::string command2 = "G()()()()(al)";
    std::string command3 = "(al)G(al)()()G";
    
    std::cout << solution.interpret(command1) << std::endl; // Output: "Goal"
    std::cout << solution.interpret(command2) << std::endl; // Output: "Gooooal"
    std::cout << solution.interpret(command3) << std::endl; // Output: "alGalooG"
    
    return 0;
}

This solution efficiently parses and translates the given command string while maintaining a linear time complexity.

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