#722

Medium

LeetCode Problem Workspace

Remove Comments

Remove comments from a given C++ program source array, handling line and block comments.

Problem Statement

You are given a C++ program represented as an array of strings, where each element of the array represents a line of code. Your task is to remove all comments from this program. In C++, comments come in two types: line comments that start with //, and block comments that are enclosed between /* and */. The program source may contain both types of comments, and your goal is to return the source code without the comments, preserving the structure of the program.

Block comments may span multiple lines, and any block comment that begins on one line must be closed by a */ on some subsequent line. Only the first active comment (whether line or block) on any line should be removed. For example, block comments must take precedence over other comments in the line.

Examples

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;","}"]

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"]

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 <= 100
0 <= source[i].length <= 80
source[i] consists of printable ASCII characters.
Every open block comment is eventually closed.
There are no single-quote or double-quote in the input.

Solution Approach

Parse each line individually

Iterate through each line of the source code, checking for the presence of either a block comment (/*) or a line comment (//). If a block comment is detected, skip over the entire block, considering multi-line continuations. If a line comment is detected, remove everything from the comment marker onward.

Handle block comments

When encountering a block comment, ensure to keep track of its start and end markers (/* and */). Ignore all content between these markers, even if they span across multiple lines. Always ensure that the block comment is properly closed before resuming parsing the code.

Concatenate the remaining code

Once comments are removed, concatenate the remaining parts of the code line by line. Ensure that the structure is maintained, meaning that lines without comments should be preserved exactly as they appear.

Complexity Analysis

Metric	Value
Time	O(S)
Space	O(S)

The time complexity of the solution is O(S), where S is the total number of characters in the input source code. This is because we examine each character once to determine whether it is part of a comment or valid code. The space complexity is also O(S) since we are constructing a new array that holds the result without the comments.

What Interviewers Usually Probe

Can the candidate correctly handle nested comments and multi-line block comments?
Is the candidate using an efficient way to skip over block comments without unnecessary operations?
Does the candidate preserve the original structure of the code after comment removal?

Common Pitfalls or Variants

Common pitfalls

Not handling multi-line block comments properly, which can lead to incorrect removal of code.
Ignoring nested comments and not processing each part of the code in the correct order.
Overcomplicating the parsing logic, making the solution more difficult to understand or less efficient.

Follow-up variants

Extend the problem to handle comments within strings or character literals.
Optimize the solution for very large input arrays with more stringent time constraints.
Modify the solution to also detect and remove deprecated or obsolete code sections along with comments.

FAQ

What is the most common challenge in solving the Remove Comments problem?

The main challenge is properly handling multi-line block comments and ensuring that comments spanning multiple lines are correctly removed without disrupting the program's structure.

How does this problem relate to parsing and string manipulation?

This problem tests your ability to parse strings efficiently while handling specific patterns like comment markers (/*, */, and //). It's a combination of string manipulation and parsing logic.

What pattern should I focus on for solving the Remove Comments problem?

The main pattern involves handling both string and array manipulations, specifically ensuring that comments are removed without disturbing the overall structure of the code.

Can I use regular expressions for this problem?

While regular expressions can be useful for detecting comment patterns, handling nested block comments and ensuring the correct removal across lines requires a more manual parsing approach.

What are some potential optimizations for solving Remove Comments?

You can optimize by ensuring that you skip over entire block comments in one go, avoiding unnecessary character-by-character checking once a block comment is found.

terminal

Solution

Solution 1: Case Analysis

We use a variable $\textit{blockComment}$ to indicate whether we are currently in a block comment. Initially, $\textit{blockComment}$ is `false`. We use a variable $t$ to store the valid characters of the current line.

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 ans

Continue Practicing

#721 accounts merge #720 longest word in dictionary #745 prefix and suffix search