Goal Parser Interpretation — Solution in Python, Java & C++
Goal Parser Interpretation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on strings.
Goal Parser Interpretation is an easy coding problem on strings, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Strings
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You own a Goal Parser that reads a string made only of "G", "()" and "(al)". It interprets "G" as "G", "()" as "o" and "(al)" as "al", then concatenates the pieces in order.
Given the string command, return the parser's interpretation.
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
Constraints
1 <= command.length <= 40command consists only of "G", "()" and "(al)" in some order.
Hints for Goal Parser Interpretation
Hint 1
Scan left to right; the character at the cursor tells you which of the three tokens starts there.
Hint 2
A
Gadvances one,()advances two,(al)advances four.Hint 3
Peeking at the next character after a
(is enough to tell()from(al).
How to solve Goal Parser Interpretation
The three tokens never overlap, so two ordered substitutions — () → o, then (al) → al — produce the interpretation.
Approach
- Replace every
()witho. - Replace every
(al)withal. - Return the result (the
Gs are unchanged).
Why it works
() and (al) cannot share characters in a valid command, and replacing () first never creates or destroys an (al). A left-to-right scan that inspects the character after each ( is the equivalent single-pass form.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Swapping the order of the two replacements is still safe here; the danger would be a replacement that produces a
(.
Reference solution
Python
def interpret(command: str) -> str:
return command.replace("()", "o").replace("(al)", "al")Java
public static String interpret(String command) {
StringBuilder out = new StringBuilder();
int i = 0;
while (i < command.length()) {
if (command.charAt(i) == 'G') {
out.append('G');
i += 1;
} else if (command.charAt(i + 1) == ')') {
out.append('o');
i += 2;
} else {
out.append("al");
i += 4;
}
}
return out.toString();
}C++
string interpret(string command) {
string out = "";
int i = 0;
int n = (int) command.size();
while (i < n) {
if (command[i] == 'G') { out += 'G'; i += 1; }
else if (command[i + 1] == ')') { out += 'o'; i += 2; }
else { out += "al"; i += 4; }
}
return out;
}JavaScript
var interpret = function(command) {
let out = "";
let i = 0;
while (i < command.length) {
if (command[i] === "G") { out += "G"; i += 1; }
else if (command[i + 1] === ")") { out += "o"; i += 2; }
else { out += "al"; i += 4; }
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings