Remove Comments
MedPrompt
Given a C++ program, remove comments from it. The program source is an array of strings source where source[i] is the ith line of the source code. This represents the result of splitting the original source code string by the newline character '\n'.
In C++, there are two types of comments, line comments, and block comments.
- The string
"//"denotes a line comment, which represents that it and the rest of the characters to the right of it in the same line should be ignored. - The string
"/*"denotes a block comment, which represents that all characters until the next (non-overlapping) occurrence of"*/"should be ignored. (Here, occurrences happen in reading order: line by line from left to right.) To be clear, the string"/*/"does not yet end the block comment, as the ending would be overlapping the beginning.
The first effective comment takes precedence over others.
- For example, if the string
"//"occurs in a block comment, it is ignored. - Similarly, if the string
"/*"occurs in a line or block comment, it is also ignored.
If a certain line of code is empty after removing comments, you must not output that line: each string in the answer list will be non-empty.
There will be no control characters, single quote, or double quote characters.
- For example,
source = "string s = "/* Not a comment. */";"will not be a test case.
Also, nothing else such as defines or macros will interfere with the comments.
It is guaranteed that every open block comment will eventually be closed, so "/*" outside of a line or block comment always starts a new comment.
Finally, implicit newline characters can be deleted by block comments. Please see the examples below for details.
After removing the comments from the source code, return the source code in the same format.
Example 1:
Input: source = ["/*Test program */", "int main()", "{ ", " // variable declaration ", "int a, b, c;", "/* This is a test", " multiline ", " comment for ", " testing */", "a = b + c;", "}"]
Output: ["int main()","{ "," ","int a, b, c;","a = b + c;","}"]
Explanation: The line by line code is visualized as below:
/*Test program */
int main()
{
// variable declaration
int a, b, c;
/* This is a test
multiline
comment for
testing */
a = b + c;
}
The string /* denotes a block comment, including line 1 and lines 6-9. The string // denotes line 4 as comments.
The line by line output code is visualized as below:
int main()
{
int a, b, c;
a = b + c;
}Example 2:
Input: source = ["a/*comment", "line", "more_comment*/b"]
Output: ["ab"]
Explanation: The original source string is "a/*comment\nline\nmore_comment*/b", where we have bolded the newline characters. After deletion, the implicit newline characters are deleted, leaving the string "ab", which when delimited by newline characters becomes ["ab"].
Constraints:
1 <= source.length <= 1000 <= source[i].length <= 80source[i]consists of printable ASCII characters.- Every open block comment is eventually closed.
- There are no single-quote or double-quote in the input.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach leverages the power of regular expressions to solve the problem in a very concise way. It works by first consolidating the entire source code into a single string. Then, a carefully crafted regular expression is used to find and eliminate all occurrences of both line (//) and block (/* ... */) comments in one go. Finally, the cleaned string is split back into individual lines, and any empty lines are discarded.
Algorithm
- Join the
sourcearray into a single stringcodeseparated by\n. - Define a regular expression
//.*|/\*[\s\S]*?\*/to match both line and block comments. - Use
String.replaceAll()to replace all occurrences of comments incodewith an empty string. - Split the resulting string by
\nto get an array of lines. - Filter out any empty strings from the array.
- Convert the result to a list and return it.
Walkthrough
The core of this method is a single, powerful regular expression: //.*|/\*[\s\S]*?\*/. Let's break it down:
//.*: This part matches a//sequence followed by any character (.) zero or more times (*) until the end of the line. This handles line comments.|: This is the OR operator, allowing the regex to match either the pattern on its left or the one on its right./\*[\s\S]*?\*/: This part handles block comments.\*is an escaped asterisk to match the literal*character.[\s\S]matches any whitespace or non-whitespace character (effectively, any character including newlines). The*?makes the match non-greedy, so it stops at the first*/it finds.
The implementation steps are:
- Join all lines from the
sourcearray into a single string, using\nas the delimiter. - Apply the
replaceAllmethod with the regex to this string. - Split the result of the replacement by
\n. - Stream the resulting array, filter out empty lines, and collect the results into a list.
import java.util.ArrayList;import java.util.List;import java.util.Arrays;import java.util.stream.Collectors; class Solution { public List<String> removeComments(String[] source) { String sourceCode = String.join("\n", source); String noComments = sourceCode.replaceAll("//.*|/\\*[\\s\\S]*?\\*/", ""); if (noComments.isEmpty()) { return new ArrayList<>(); } return Arrays.stream(noComments.split("\n")) .filter(line -> !line.isEmpty()) .collect(Collectors.toList()); }}Complexity
Time
O(C), where C is the total number of characters in the source. While theoretically linear, the constant factor for regex processing is typically higher than for manual parsing. Operations like `join`, `replaceAll`, and `split` all take time proportional to the content size.
Space
O(C), where C is the total number of characters in the source. This approach requires space to store the joined string, the result of the `replaceAll` operation, and the final list of strings.
Trade-offs
Pros
The code is very concise and high-level.
It leverages Java's built-in, highly optimized regex engine.
Reduces the amount of manual state management code.
Cons
Regex can be difficult to write, read, and debug correctly for all edge cases.
The performance is generally worse than manual parsing due to the overhead of the generic regex engine.
Creates large intermediate strings for the entire source code, which can be memory-intensive, potentially using up to 3x the original source size in memory.
This approach simulates the process of a compiler's preprocessor by iterating through the source code character by character, line by line. It uses a state machine with a single boolean flag, inBlockComment, to track whether the current character is inside a block comment. By processing the source in a single pass, it efficiently builds the resulting code lines without creating large intermediate strings.
Algorithm
- Initialize an empty list
result, a boolean flaginBlockComment, and an emptyStringBuilder sb. - Loop through each
linein thesourcearray. - For each
line, loop through its characters from left to right. - If
inBlockCommentistrue, look for a*/sequence. If found, setinBlockCommenttofalseand skip the two characters. - If
inBlockCommentisfalse, check for comment starters:- If
//is found, break the inner loop to ignore the rest of the line. - If
/*is found, setinBlockCommenttotrueand skip the two characters. - Otherwise, append the character to
sb.
- If
- After each line is processed, if
inBlockCommentisfalseandsbhas content, addsb.toString()toresultand resetsb. - Return
resultafter all lines are processed.
Walkthrough
This method processes the source code in a single pass, which is optimal in terms of time and space. We maintain a state, inBlockComment, to know if we are currently parsing inside a block comment.
A StringBuilder is used to construct the current line of output code. This is crucial because a block comment can start on one line and end on another, effectively merging the code before the /* with the code after the */ into a single line.
The logic proceeds as follows:
- We iterate through each line of the
sourcearray. - For each line, we iterate through its characters.
- If we are in a block comment (
inBlockComment == true), we simply scan for the closing*/. Once found, we switch the state back and continue parsing from the next character. - If we are not in a block comment, we check for the start of either a line comment (
//) or a block comment (/*).- If
//is found, we can ignore the rest of the line. - If
/*is found, we switch our state toinBlockCommentand continue. - If neither is found, the character is part of the code and is appended to our
StringBuilder.
- If
- After each line from the input is fully processed, if we are not in a block comment and have accumulated some code in our
StringBuilder, we add it as a new line to our result and clear the builder.
import java.util.ArrayList;import java.util.List; class Solution { public List<String> removeComments(String[] source) { List<String> result = new ArrayList<>(); StringBuilder sb = new StringBuilder(); boolean inBlockComment = false; for (String line : source) { for (int i = 0; i < line.length(); i++) { if (inBlockComment) { if (i + 1 < line.length() && line.charAt(i) == '*' && line.charAt(i + 1) == '/') { inBlockComment = false; i++; // Skip the '/' } } else { if (i + 1 < line.length() && line.charAt(i) == '/' && line.charAt(i + 1) == '/') { break; // Ignore the rest of the line } else if (i + 1 < line.length() && line.charAt(i) == '/' && line.charAt(i + 1) == '*') { inBlockComment = true; i++; // Skip the '*' } else { sb.append(line.charAt(i)); } } } if (!inBlockComment && sb.length() > 0) { result.add(sb.toString()); sb = new StringBuilder(); } } return result; }}Complexity
Time
O(C), where C is the total number of characters in the source code. This is the most efficient possible time complexity as we must look at every character at least once.
Space
O(C), where C is the total number of characters. The space is dominated by the `result` list and the `StringBuilder`, which in the worst case (no comments) will hold a copy of the entire source code.
Trade-offs
Pros
Optimal time complexity, as it processes each character of the input exactly once.
Optimal space complexity, as it avoids creating large intermediate copies of the entire source code.
Handles all edge cases correctly by design, such as comments spanning multiple lines or multiple comment types on a single line.
Cons
The logic is more complex and requires careful, explicit state management.
The code is more verbose compared to a high-level regex approach.
Solutions
Solution
class Solution {public List<String> removeComments(String[] source) { List<String> ans = new ArrayList<>(); StringBuilder sb = new StringBuilder(); boolean blockComment = false; for (String s : source) { int m = s.length(); for (int i = 0; i < m; ++i) { if (blockComment) { if (i + 1 < m && s.charAt(i) == '*' && s.charAt(i + 1) == '/') { blockComment = false; ++i; } } else { if (i + 1 < m && s.charAt(i) == '/' && s.charAt(i + 1) == '*') { blockComment = true; ++i; } else if (i + 1 < m && s.charAt(i) == '/' && s.charAt(i + 1) == '/') { break; } else { sb.append(s.charAt(i)); } } } if (!blockComment && sb.length() > 0) { ans.add(sb.toString()); sb.setLength(0); } } return ans; }}class Solution {public: vector<string> removeComments(vector<string> &source) { vector<string> ans; string t; bool blockComment = false; for (auto &s : source) { int m = s.size(); for (int i = 0; i < m; ++i) { if (blockComment) { if (i + 1 < m && s[i] == '*' && s[i + 1] == '/') { blockComment = false; ++i; } } else { if (i + 1 < m && s[i] == '/' && s[i + 1] == '*') { blockComment = true; ++i; } else if (i + 1 < m && s[i] == '/' && s[i + 1] == '/') { break; } else { t.push_back(s[i]); } } } if (!blockComment && !t.empty()) { ans.emplace_back(t); t.clear(); } } return ans; }};class Solution: def removeComments(self, source: List[str]) -> List[str]: ans = [] t = [] block_comment = False for s in source: i, m = 0, len(s) while i < m: if block_comment: if i + 1 < m and s[i: i + 2] == "*/": block_comment = False i += 1 else: if i + 1 < m and s[i: i + 2] == "/*": block_comment = True i += 1 elif i + 1 < m and s[i: i + 2] == "//": break else: t . append(s[i]) i += 1 if not block_comment and t: ans . append("" . join(t)) t . clear() return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.