Remove Comments
Remove Comments is a medium arrays & hashing problem solved with the simulation pattern.
The best approach, optimal (line-by-line state machine), runs in O(L) time and O(L) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from join and scan up.
Problem
You are given a program as an array of lines, source. Strip out all comments and return the remaining code as an array of lines.
There are two kinds of comments. // starts a line comment: it and everything after it on that line are removed. /* starts a block comment: everything up to and including the next */ is removed, even across several lines; when that happens the code before the comment and the code after it become one line. Whichever marker appears first wins, so // or /* inside a comment has no special meaning.
After removing comments, leave out every line that is empty. Keep everything else exactly as it is, spaces included.
Examples
Example 1
- Input
source = ["int a = 1; // set a", "/* block", "still block */int b;", "return a + b;"]- Output
["int a = 1; ", "int b;", "return a + b;"]- Why
- The line comment removes the rest of line 1. The block comment covers the end of line 2 and the start of line 3, so only "int b;" survives from those two lines.
Example 2
- Input
source = ["x = 4/*cut*/2;"]- Output
["x = 42;"]- Why
- A block comment can sit in the middle of a line; the text on both sides joins up.
Example 3
- Input
source = ["a/*", "*/b", "// only comment"]- Output
["ab"]- Why
- The block comment swallows the line break, so a and b end up on one line. The last line becomes empty and is dropped.
Constraints
1 <= source.length <= 1000 <= source[i].length <= 80source[i]consists of printable ASCII characters (no quotes need special handling).- Every
/*that starts a block comment is closed by a later*/.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Join and scan | O(L) | O(L) |
| Optimal (line-by-line state machine) | O(L) | O(L) |
1Join and scan
O(L)Every character of the joined text (L characters in total) is looked at a constant number of times.O(L)The joined text and the filtered copy are both up to L characters.Glue the lines together with newline characters, so a block comment simply removes everything up to its */, newlines included. Scan the big string once, copying characters that are not inside comments; a line comment stops just before the next newline. Finally split on newlines and drop empty lines.
- text = all lines joined with '\n'.
- At '//', skip forward to the next '\n' (keep the newline itself).
- At '/', skip past the matching '/' (start looking two characters later so '/*/' does not close it).
- Otherwise copy the character.
- Split the result on '\n' and keep the non-empty pieces.
class Solution {
public List<String> removeComments(String[] source) {
String text = String.join("\n", source);
int n = text.length();
StringBuilder out = new StringBuilder();
int i = 0;
while (i < n) {
if (i + 1 < n && text.charAt(i) == '/' && text.charAt(i + 1) == '/') {
while (i < n && text.charAt(i) != '\n') i++;
} else if (i + 1 < n && text.charAt(i) == '/' && text.charAt(i + 1) == '*') {
i += 2;
while (!(text.charAt(i) == '*' && text.charAt(i + 1) == '/')) i++;
i += 2;
} else {
out.append(text.charAt(i));
i++;
}
}
List<String> res = new ArrayList<>();
for (String line : out.toString().split("\n")) {
if (!line.isEmpty()) res.add(line);
}
return res;
}
}class Solution:
def removeComments(self, source: List[str]) -> List[str]:
text = "\n".join(source)
n = len(text)
out: List[str] = []
i = 0
while i < n:
if text.startswith("//", i):
while i < n and text[i] != "\n":
i += 1
elif text.startswith("/*", i):
i = text.index("*/", i + 2) + 2
else:
out.append(text[i])
i += 1
return [line for line in "".join(out).split("\n") if line]class Solution {
public:
vector<string> removeComments(vector<string>& source) {
string text;
for (size_t k = 0; k < source.size(); k++) {
if (k > 0) text += '\n';
text += source[k];
}
int n = text.size();
string out;
int i = 0;
while (i < n) {
if (i + 1 < n && text[i] == '/' && text[i + 1] == '/') {
while (i < n && text[i] != '\n') i++;
} else if (i + 1 < n && text[i] == '/' && text[i + 1] == '*') {
i += 2;
while (!(text[i] == '*' && text[i + 1] == '/')) i++;
i += 2;
} else {
out += text[i];
i++;
}
}
vector<string> res;
string line;
for (char c : out) {
if (c == '\n') {
if (!line.empty()) res.push_back(line);
line.clear();
} else {
line += c;
}
}
if (!line.empty()) res.push_back(line);
return res;
}
};function removeComments(source) {
const text = source.join("\n");
const n = text.length;
let out = "";
let i = 0;
while (i < n) {
if (text.startsWith("//", i)) {
while (i < n && text[i] !== "\n") i++;
} else if (text.startsWith("/*", i)) {
i = text.indexOf("*/", i + 2) + 2;
} else {
out += text[i];
i++;
}
}
return out.split("\n").filter((line) => line.length > 0);
}2Optimal (line-by-line state machine)
O(L)Each character of the input is visited once; L is the total number of characters.O(L)The buffer and the answer together hold at most the surviving characters.Process the lines in order with a flag inBlock and a buffer for the output line being built. Outside a block, copy characters until // (drop the rest of the line) or /* (enter the block). Inside a block, skip characters until */. At the end of each input line, emit the buffer only if you are not inside a block and it is non-empty.
- inBlock = false, buf = empty.
- For each line, scan i from 0: if inBlock and the next two characters are '*/', leave the block and skip both; if inBlock otherwise, skip one character.
- If not inBlock: on '/*' enter the block and skip two; on '//' stop scanning this line; else append the character to buf.
- After the line: if not inBlock and buf is non-empty, add buf to the answer and clear it.
- Return the answer.
class Solution {
public List<String> removeComments(String[] source) {
List<String> res = new ArrayList<>();
StringBuilder buf = new StringBuilder();
boolean inBlock = false;
for (String line : source) {
int n = line.length();
int i = 0;
while (i < n) {
char c = line.charAt(i);
char next = i + 1 < n ? line.charAt(i + 1) : 0;
if (inBlock) {
if (c == '*' && next == '/') {
inBlock = false;
i += 2;
} else {
i++;
}
} else if (c == '/' && next == '*') {
inBlock = true;
i += 2;
} else if (c == '/' && next == '/') {
break;
} else {
buf.append(c);
i++;
}
}
if (!inBlock && buf.length() > 0) {
res.add(buf.toString());
buf.setLength(0);
}
}
return res;
}
}class Solution:
def removeComments(self, source: List[str]) -> List[str]:
res: List[str] = []
buf: List[str] = []
in_block = False
for line in source:
n = len(line)
i = 0
while i < n:
c = line[i]
nxt = line[i + 1] if i + 1 < n else ""
if in_block:
if c == "*" and nxt == "/":
in_block = False
i += 2
else:
i += 1
elif c == "/" and nxt == "*":
in_block = True
i += 2
elif c == "/" and nxt == "/":
break
else:
buf.append(c)
i += 1
if not in_block and buf:
res.append("".join(buf))
buf = []
return resclass Solution {
public:
vector<string> removeComments(vector<string>& source) {
vector<string> res;
string buf;
bool inBlock = false;
for (const string& line : source) {
int n = line.size();
int i = 0;
while (i < n) {
char c = line[i];
char next = i + 1 < n ? line[i + 1] : 0;
if (inBlock) {
if (c == '*' && next == '/') {
inBlock = false;
i += 2;
} else {
i++;
}
} else if (c == '/' && next == '*') {
inBlock = true;
i += 2;
} else if (c == '/' && next == '/') {
break;
} else {
buf += c;
i++;
}
}
if (!inBlock && !buf.empty()) {
res.push_back(buf);
buf.clear();
}
}
return res;
}
};function removeComments(source) {
const res = [];
let buf = "";
let inBlock = false;
for (const line of source) {
const n = line.length;
let i = 0;
while (i < n) {
const c = line[i];
const next = i + 1 < n ? line[i + 1] : "";
if (inBlock) {
if (c === "*" && next === "/") {
inBlock = false;
i += 2;
} else {
i++;
}
} else if (c === "/" && next === "*") {
inBlock = true;
i += 2;
} else if (c === "/" && next === "/") {
break;
} else {
buf += c;
i++;
}
}
if (!inBlock && buf.length > 0) {
res.push(buf);
buf = "";
}
}
return res;
}Edge cases to test
- A block comment that spans several lines joins the text before it with the text after it
//inside a block comment and/*inside a line comment mean nothing/*/does not close the comment it opens: the*is already part of the opener- Lines that become empty after removing comments are left out of the answer
Hints
Hint 1
Scan character by character and keep one flag: are you inside a block comment right now?
Hint 2
Outside a block, // ends the useful part of the line and /* turns the flag on. Inside, only */ matters.
Hint 3
Do not flush the current line while still inside a block comment: the text after */ belongs to the same output line.
FAQ
What is the best time complexity for Remove Comments?
Optimal (line-by-line state machine) runs in O(L) time and O(L) extra space. Each character of the input is visited once; L is the total number of characters.
Which pattern does Remove Comments use?
It is a arrays & hashing problem that uses the simulation pattern. Other problems with the same pattern: Text Justification, Integer to English Words, String to Integer (atoi).
Is there a brute force solution for Remove Comments?
Yes. Join and scan takes O(L) time and O(L) space. Glue the lines together with newline characters, so a block comment simply removes everything up to its /, newlines included.
Which edge cases should I test for Remove Comments?
A block comment that spans several lines joins the text before it with the text after it; // inside a block comment and / inside a line comment mean nothing; // does not close the comment it opens: the is already part of the opener; Lines that become empty after removing comments are left out of the answer.