algoadvance

Leetcode 722. Remove Comments

Problem Statement

The problem involves removing comments from a source code represented as a list of strings. In the code, comments can be either:

  1. Line comments starting with // which extend to the end of the current line.
  2. Block comments starting with /* and ending with */ which can span multiple lines.

The task is to return the source code after removing all the comments.

Clarifying Questions

  1. Input Format: Is the input always a valid source code i.e., it doesn’t have unclosed block comments?
    • Assumption: Yes, the input is always valid as per the problem constraints.
  2. Output Format: Should each line in the output be a string?
    • Assumption: Yes, the output should be a list of strings where each string represents a line of the source code with comments removed.
  3. Handling Edge Cases: Should we handle empty lines or lines with only spaces after comment removal?
    • Assumption: Yes, they should be handled accordingly and not included in the final output if they are empty.

Strategy

  1. Initialize State: Use a boolean flag to track whether we are inside a block comment.
  2. Iterate Through Each Line: Process each line character by character.
    • If inside a block comment, continue until the block is closed.
    • If a line comment starts, ignore the rest of the line.
    • If a block comment starts, set the block comment flag.
  3. Construct the Output: Add non-comment parts of the line to a temporary list. Once iteration ends, add non-empty lines to the result.

Code

Here’s a possible C++ implementation:

#include <vector>
#include <string>

std::vector<std::string> removeComments(std::vector<std::string>& source) {
    std::vector<std::string> result;
    bool inBlockComment = false;
    std::string newLine;
    
    for (const std::string &line : source) {
        int i = 0;
        if (!inBlockComment) newLine.clear();  // start fresh if not in block comment
        
        while (i < line.length()) {
            if (!inBlockComment && i + 1 < line.length() && line[i] == '/' && line[i + 1] == '*') {
                inBlockComment = true;
                i += 2;  // skip the "/*"
            } else if (inBlockComment && i + 1 < line.length() && line[i] == '*' && line[i + 1] == '/') {
                inBlockComment = false;
                i += 2;  // skip the "*/"
            } else if (!inBlockComment && i + 1 < line.length() && line[i] == '/' && line[i + 1] == '/') {
                break;  // ignore the rest of the line
            } else if (!inBlockComment) {
                newLine.push_back(line[i]);
                i++;
            } else {
                i++;
            }
        }
        
        if (!inBlockComment && !newLine.empty()) {
            result.push_back(newLine);
        }
    }
    
    return result;
}

Time Complexity

The time complexity of this solution is O(n * m), where ( n ) is the number of lines and ( m ) is the maximum length of a line. This is because in the worst case, we iterate through each character of all lines.

By following this structured approach, we ensure that the solution is both efficient and easy to understand.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI