{"id":9199,"date":"2021-12-23T05:27:19","date_gmt":"2021-12-23T13:27:19","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9199"},"modified":"2021-12-23T12:10:14","modified_gmt":"2021-12-23T20:10:14","slug":"leetcode-722-remove-comments","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-722-remove-comments\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 722. Remove Comments"},"content":{"rendered":"\n<p>Given a C++ program, remove comments from it. The program source is an array of strings&nbsp;<code>source<\/code>&nbsp;where&nbsp;<code>source[i]<\/code>&nbsp;is the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;line of the source code. This represents the result of splitting the original source code string by the newline character&nbsp;<code>'\\n'<\/code>.<\/p>\n\n\n\n<p>In C++, there are two types of comments, line comments, and block comments.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The string&nbsp;<code>\"\/\/\"<\/code>&nbsp;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.<\/li><li>The string&nbsp;<code>\"\/*\"<\/code>&nbsp;denotes a block comment, which represents that all characters until the next (non-overlapping) occurrence of&nbsp;<code>\"*\/\"<\/code>&nbsp;should be ignored. (Here, occurrences happen in reading order: line by line from left to right.) To be clear, the string&nbsp;<code>\"\/*\/\"<\/code>&nbsp;does not yet end the block comment, as the ending would be overlapping the beginning.<\/li><\/ul>\n\n\n\n<p>The first effective comment takes precedence over others.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, if the string&nbsp;<code>\"\/\/\"<\/code>&nbsp;occurs in a block comment, it is ignored.<\/li><li>Similarly, if the string&nbsp;<code>\"\/*\"<\/code>&nbsp;occurs in a line or block comment, it is also ignored.<\/li><\/ul>\n\n\n\n<p>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.<\/p>\n\n\n\n<p>There will be no control characters, single quote, or double quote characters.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example,&nbsp;<code>source = \"string s = \"\/* Not a comment. *\/\";\"<\/code>&nbsp;will not be a test case.<\/li><\/ul>\n\n\n\n<p>Also, nothing else such as defines or macros will interfere with the comments.<\/p>\n\n\n\n<p>It is guaranteed that every open block comment will eventually be closed, so&nbsp;<code>\"\/*\"<\/code>&nbsp;outside of a line or block comment always starts a new comment.<\/p>\n\n\n\n<p>Finally, implicit newline characters can be deleted by block comments. Please see the examples below for details.<\/p>\n\n\n\n<p>After removing the comments from the source code, return&nbsp;<em>the source code in the same format<\/em>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> source = [\"\/*Test program *\/\", \"int main()\", \"{ \", \"  \/\/ variable declaration \", \"int a, b, c;\", \"\/* This is a test\", \"   multiline  \", \"   comment for \", \"   testing *\/\", \"a = b + c;\", \"}\"]\n<strong>Output:<\/strong> [\"int main()\",\"{ \",\"  \",\"int a, b, c;\",\"a = b + c;\",\"}\"]\n<strong>Explanation:<\/strong> The line by line code is visualized as below:\n\/*Test program *\/\nint main()\n{ \n  \/\/ variable declaration \nint a, b, c;\n\/* This is a test\n   multiline  \n   comment for \n   testing *\/\na = b + c;\n}\nThe string \/* denotes a block comment, including line 1 and lines 6-9. The string \/\/ denotes line 4 as comments.\nThe line by line output code is visualized as below:\nint main()\n{ \n  \nint a, b, c;\na = b + c;\n}\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> source = [\"a\/*comment\", \"line\", \"more_comment*\/b\"]\n<strong>Output:<\/strong> [\"ab\"]\n<strong>Explanation:<\/strong> 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\"].\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= source.length &lt;= 100<\/code><\/li><li><code>0 &lt;= source[i].length &lt;= 80<\/code><\/li><li><code>source[i]<\/code>&nbsp;consists of printable&nbsp;<strong>ASCII<\/strong>&nbsp;characters.<\/li><li>Every open block comment is eventually closed.<\/li><li>There are no single-quote or&nbsp;double-quote in the input.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Marking the block<\/strong><\/h2>\n\n\n\n<p>The key of this problem is to mark the start and end of a block comment and handling new lines.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n) -&gt; O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<string> removeComments(vector<string>& source) {\n    vector<string> ans;\n    bool block = false;\n    string output;\n    for (string_view line : source) {      \n      for (int i = 0, n = line.size(); i < n; ++i) {\n        if (block) {\n          if (line.substr(i, 2) == \"*\/\") {\n            block = false; \/\/ leaving block.\n            ++i;\n          }\n          \/\/ skip all characters inside the block.\n        } else if (line.substr(i, 2) == \"\/*\") {\n          block = true; \/\/ entering block.\n          ++i;\n        } else if (line.substr(i, 2) == \"\/\/\") {\n          break;\/\/ skip the remaining part of the line.\n        } else {\n          output += line[i];\n        }\n      }\n      if (!block and !output.empty())\n        ans.push_back(std::move(output)); \/\/ output cleared.\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a C++ program, remove comments from it. The program source is an array of strings&nbsp;source&nbsp;where&nbsp;source[i]&nbsp;is the&nbsp;ith&nbsp;line of the source code. This represents the result&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47],"tags":[177,4,504],"class_list":["post-9199","post","type-post","status-publish","format-standard","hentry","category-string","tag-medium","tag-string","tag-text","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9199","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9199"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9199\/revisions"}],"predecessor-version":[{"id":9203,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9199\/revisions\/9203"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9199"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9199"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9199"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}