删除注释

标签: 数组字符串

难度: 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 字符组成。
每个块注释都会被闭合。
给定的源码中不会有单引号、双引号或其他控制字符。

Submission

运行时间: 29 ms

内存: 16.0 MB

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

Explain

这个题解是用迭代的方式来处理每一行代码。它维护了一个布尔变量 in_block_comment 来表示当前是否处于块注释中，以及一个字符串 current_line 来存储当前正在构建的有效代码行。通过遍历每一行代码中的每个字符，根据不同的情况来判断是否需要忽略某些字符： 1. 如果当前不在块注释中，并且遇到了 /* ，则进入块注释状态； 2. 如果当前在块注释中，并且遇到了 */ ，则退出块注释状态； 3. 如果当前不在块注释中，并且遇到了 // ，则忽略该行的剩余部分； 4. 如果当前不在块注释中，则将当前字符加入 current_line 。在处理完每一行后，如果当前不在块注释中并且 current_line 不为空，则将 current_line 加入结果列表 result ，并清空 current_line 以便处理下一行。

时间复杂度: O(n * m)

空间复杂度: O(n)

class Solution:
    def removeComments(self, source: List[str]) -> List[str]:
        result = []
        in_block_comment = False
        current_line = ''
        
        for line in source:  # 遍历每一行代码
            i = 0
            while i < len(line):  # 遍历当前行的每个字符
                if not in_block_comment and i + 1 < len(line) and line[i:i+2] == '/*':  # 进入块注释
                    in_block_comment = True
                    i += 1
                elif in_block_comment and i + 1 < len(line) and line[i:i+2] == '*/':  # 退出块注释
                    in_block_comment = False
                    i += 1
                elif not in_block_comment and i + 1 < len(line) and line[i:i+2] == '//':  # 忽略行注释
                    break
                elif not in_block_comment:  # 当前字符是有效代码
                    current_line += line[i]
                i += 1
            
            if not in_block_comment and current_line:  # 当前行处理完毕，且不在块注释中
                result.append(current_line)  # 将当前行加入结果列表
                current_line = ''  # 清空当前行
        
        return result

Explore

在算法实现中，当检测到`/*`时，会立即进入块注释状态，并将索引`i`增加以跳过`/*`。接下来的迭代中，如果紧接着出现`*/`，即使它们是连续的，算法也会识别并处理这种情况。具体来说，当`i`和`i+1`位置上的字符是`*/`时，它会将`in_block_comment`标志设为`false`并将`i`再次增加，从而正确退出块注释状态。因此，无论`/*`和`*/`是否紧密相连，算法都能正确处理块注释的开始和结束。

根据算法的逻辑，当遇到行注释标志`//`，算法会忽略该行剩余的所有字符，包括任何出现的`/*`。这意味着，在行注释开始之后的所有内容，无论是另一个注释的开始符号还是其他任何字符，都会被算法忽视，不会对块注释状态造成影响。因此，如果在`//`之后出现`/*`，它将被视为行注释的一部分并被忽略。

在算法中，每次识别到块注释的开始(`/*`)或结束(`*/`)时，`i`会增加以跳过这两个字符。这确保了`/*`和`*/`本身不会被加入到最终的代码行中。但是，紧跟在`*/`之后的字符不会被忽略；索引`i`在处理完`*/`后会指向`*/`之后的下一个字符，然后继续正常处理这些字符。只有当结束块注释的同时达到行的末尾，后续字符才不会被处理，但这是由于行的结束，而非注释处理逻辑本身。

根据算法的设计，如果在处理完一行后仍处于块注释状态，该行中任何在块注释开始之前的有效代码都不会被添加到最终的结果中。`current_line`仅在不处于块注释状态时才会被添加到结果列表`result`中。这意味着，即使在块注释开始之前的部分有有效代码，如果块注释没有在该行结束，这部分代码也会被丢弃，只有当块注释结束后，后续行中的代码才会被处理并可能被添加到结果中。