Medium

题目描述

给一个 C++ 程序，请去掉程序中的注释。这个程序的源码字符串数组为 source，其中 source[i] 表示第 i 行源码。这相当于把原始源码字符串按换行符 '\n' 分割的结果。

在 C++ 中，有两种类型的注释，行注释和块注释。

  • 字符串 "//" 表示行注释，表示 "//" 和其右侧的其余字符应该被忽略。
  • 字符串 "/*" 表示块注释，表示在下一个（非重叠）出现的 "*/" 之前的所有字符都应该被忽略。（这里，出现是按阅读顺序：从左到右逐行。）为了清楚起见，字符串 "/*/" 并不表示块注释的结束，因为结尾会与开头重叠。

第一个有效的注释优先于其他注释。

  • 例如，如果字符串 "//" 出现在块注释中，它将被忽略。
  • 类似地，如果字符串 "/*" 出现在行注释或块注释中，它也会被忽略。

如果一行在移除注释之后变为空行，你不要输出它；答案列表中的每个字符串都是非空的。

输入中不会有控制字符，单引号，或双引号字符。

  • 例如，source = "string s = "/* Not a comment. */";"不会成为测试用例。

另外，没有其他的宏定义或语句会干扰注释。

保证每一个开始的块注释都会被关闭，所以在字符串或块注释之外的 "/*" 总是开始一个新的注释。

最后，隐式的换行符可以通过块注释删除。请看下面的例子了解详细信息。

在从源代码中删除注释后，需要用相同的格式返回源代码。

示例 1:

输入: source = ["/*Test program */", "int main()", "{ ", "  // variable declaration ", "int a, b, c;", "/* This is a test", "   multiline  ", "   comment for ", "   testing */", "a = b + c;", "}"]
输出: ["int main()","{ ","  ","int a, b, c;","a = b + c;","}"]
解释: 示例代码可以编排成这样:
/*Test program */
int main()
{ 
  // variable declaration 
int a, b, c;
/* This is a test
   multiline  
   comment for 
   testing */
a = b + c;
}
第 1 行和第 6-9 行的字符串 /* 表示块注释。第 4 行的字符串 // 表示行注释。
编排后: 
int main()
{ 
  
int a, b, c;
a = b + c;
}

示例 2:

输入: source = ["a/*comment", "line", "more_comment*/b"]
输出: ["ab"]
解释: 原始的 source 字符串是 "a/*comment\nline\nmore_comment*/b", 其中我们用粗体显示了换行符。删除注释后，隐含的换行符被删除，留下字符串 "ab" 用换行符分隔成 ["ab"]。

约束:

  • 1 <= source.length <= 100
  • 0 <= source[i].length <= 80
  • source[i] 由可打印的 ASCII 字符组成。
  • 每个打开的块注释都会被关闭。
  • 给定的源码中不会有单引号、双引号字符。

解题思路

这个问题需要我们逐字符解析源代码，识别并移除注释。关键在于正确处理两种注释类型的状态转换。

解题思路：

使用状态机的思想，维护一个布尔变量表示当前是否在块注释内。逐行、逐字符遍历源代码：

  1. 状态维护：用 inBlock 表示是否在块注释内
  2. 字符扫描：对每一行的每个字符进行扫描
  3. 注释识别：
    • 遇到 /* 且不在块注释内：进入块注释状态
    • 遇到 */ 且在块注释内：退出块注释状态
    • 遇到 // 且不在块注释内：忽略当前行剩余部分
  4. 字符处理：只有不在注释内的字符才加入结果
  5. 行处理：每行结束时，如果不在块注释内且当前行非空，则加入结果

注意事项：

  • 块注释可以跨越多行，所以需要在行间保持状态
  • 行注释只影响当前行
  • 空行不输出
  • 块注释内的 // 和行注释内的 /* 都要忽略

时间复杂度主要取决于总字符数，空间复杂度为构建结果所需的空间。

代码实现

class Solution {
public:
    vector<string> removeComments(vector<string>& source) {
        vector<string> result;
        bool inBlock = false;
        string newline = "";
        
        for (string& line : source) {
            int i = 0;
            if (!inBlock) newline = "";
            
            while (i < line.length()) {
                if (!inBlock && i + 1 < line.length() && line.substr(i, 2) == "/*") {
                    inBlock = true;
                    i += 2;
                } else if (inBlock && i + 1 < line.length() && line.substr(i, 2) == "*/") {
                    inBlock = false;
                    i += 2;
                } else if (!inBlock && i + 1 < line.length() && line.substr(i, 2) == "//") {
                    break;
                } else if (!inBlock) {
                    newline += line[i];
                    i++;
                } else {
                    i++;
                }
            }
            
            if (!inBlock && !newline.empty()) {
                result.push_back(newline);
            }
        }
        
        return result;
    }
};

class Solution:
    def removeComments(self, source: List[str]) -> List[str]:
        result = []
        in_block = False
        newline = ""
        
        for line in source:
            i = 0
            if not in_block:
                newline = ""
                
            while i < len(line):
                if not in_block and i + 1 < len(line) and line[i:i+2] == "/*":
                    in_block = True
                    i += 2
                elif in_block and i + 1 < len(line) and line[i:i+2] == "*/":
                    in_block = False
                    i += 2
                elif not in_block and i + 1 < len(line) and line[i:i+2] == "//":
                    break
                elif not in_block:
                    newline += line[i]
                    i += 1
                else:
                    i += 1
                    
            if not in_block and newline:
                result.append(newline)
                
        return result

public class Solution {
    public IList<string> RemoveComments(string[] source) {
        var result = new List<string>();
        bool inBlock = false;
        var newline = new StringBuilder();
        
        foreach (string line in source) {
            int i = 0;
            if (!inBlock) newline.Clear();
            
            while (i < line.Length) {
                if (!inBlock && i + 1 < line.Length && line.Substring(i, 2) == "/*") {
                    inBlock = true;
                    i += 2;
                } else if (inBlock && i + 1 < line.Length && line.Substring(i, 2) == "*/") {
                    inBlock = false;
                    i += 2;
                } else if (!inBlock && i + 1 < line.Length && line.Substring(i, 2) == "//") {
                    break;
                } else if (!inBlock) {
                    newline.Append(line[i]);
                    i++;
                } else {
                    i++;
                }
            }
            
            if (!inBlock && newline.Length > 0) {
                result.Add(newline.ToString());
            }
        }
        
        return result;
    }
}

var removeComments = function(source) {
    let result = [];
    let inBlockComment = false;
    let currentLine = "";
    
    for (let line of source) {
        let i = 0;
        
        if (!inBlockComment) {
            currentLine = "";
        }
        
        while (i < line.length) {
            if (!inBlockComment) {
                if (i < line.length - 1 && line.substring(i, i + 2) === "/*") {
                    inBlockComment = true;
                    i += 2;
                } else if (i < line.length - 1 && line.substring(i, i + 2) === "//") {
                    break;
                } else {
                    currentLine += line[i];
                    i++;
                }
            } else {
                if (i < line.length - 1 && line.substring(i, i + 2) === "*/") {
                    inBlockComment = false;
                    i += 2;
                } else {
                    i++;
                }
            }
        }
        
        if (!inBlockComment && currentLine.length > 0) {
            result.push(currentLine);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(N)N为源代码中所有字符的总数，需要逐字符扫描
空间复杂度O(N)主要用于存储结果和临时字符串构建

相关题目