# Remove Comments
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/remove-comments)
Canonical: https://scaleengineer.com/dsa/problems/remove-comments
**Data structures:** Array, String
**Companies:** [Hudson River Trading](https://scaleengineer.com/companies/hudson-river-trading)
---
## Problem
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 <= 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.

# Approaches
## Regular Expression Based Replacement
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.
**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.
**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.
### Explanation
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:
1.  Join all lines from the `source` array into a single string, using `\n` as the delimiter.
2.  Apply the `replaceAll` method with the regex to this string.
3.  Split the result of the replacement by `\n`.
4.  Stream the resulting array, filter out empty lines, and collect the results into a list.

```java
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());
    }
}
```
### Algorithm
- Join the `source` array into a single string `code` separated by `\n`.
- Define a regular expression `//.*|/\*[\s\S]*?\*/` to match both line and block comments.
- Use `String.replaceAll()` to replace all occurrences of comments in `code` with an empty string.
- Split the resulting string by `\n` to get an array of lines.
- Filter out any empty strings from the array.
- Convert the result to a list and return it.

## Single Pass with State Machine
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.
**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.
**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.
### Explanation
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 `source` array.
- 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 to `inBlockComment` and continue.
  - If neither is found, the character is part of the code and is appended to our `StringBuilder`.
- 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.

```java
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;
    }
}
```
### Algorithm
- Initialize an empty list `result`, a boolean flag `inBlockComment`, and an empty `StringBuilder sb`.
- Loop through each `line` in the `source` array.
- For each `line`, loop through its characters from left to right.
- If `inBlockComment` is `true`, look for a `*/` sequence. If found, set `inBlockComment` to `false` and skip the two characters.
- If `inBlockComment` is `false`, check for comment starters:
  - If `//` is found, break the inner loop to ignore the rest of the line.
  - If `/*` is found, set `inBlockComment` to `true` and skip the two characters.
  - Otherwise, append the character to `sb`.
- After each line is processed, if `inBlockComment` is `false` and `sb` has content, add `sb.toString()` to `result` and reset `sb`.
- Return `result` after all lines are processed.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```