【LeetCode-中等】722. 删除注释

题目链接

722. 删除注释

标签

字符串

步骤

Step1. 先将source合并为一个字符串进行处理，中间补上’\n’，方便后续确定注释开始、结束位置。

string combined;
for (auto str : source) {combined += str + "\n";
}

Step2. 定义数组 toDel，记录每一个注释开始、结束的位置；进行状态转移。对于 /**/ 类型的注释的结束符 */，如果匹配失败，则需要回退一位。

状态转移表示如下：

s0: if /: goto s1 # match /, change to s1else: goto s0
s1: if /: cut down this line, goto s0 # match //elif *: goto s2 # match /*else: goto s0 # match failed, return to s1
s2: if *: goto s3 # match * in comment; s2 means that the current state is InCommentelse: goto s2
s3: if /: end this comment, goto s0 # match */else: goto s3  # match failed, return to s2

具体的代码部分如下：

for (int i = 0; i < len; i++) {char ch = combined[i];switch (state) {case 0:if (ch == '/') {state = 1;} else {state = 0;}break;case 1:if (ch == '/') { // 出现//，删去此行之后的内容// 找到从当前下标开始的第一个\n，下一次遍历从其之后开始int end = combined.find("\n", i);cmtBegin = i - 1;cmtEnd = end - 1;toDel.push_back({cmtBegin, cmtEnd});state = 0;i = end;} else if (ch == '*') { // 出现/*state = 2;cmtBegin = i - 1;} else {state = 0;}break;case 2:if (ch == '*') {state = 3;} else {state = 2;}break;case 3:if (ch == '/') { // cmtEndstate = 0;cmtEnd = i;toDel.push_back({cmtBegin, cmtEnd});} else { // 匹配*/失败，回退一位state = 2;i--;}break;} 
}

Step3. 遍历 toDel，得到不含注释的中间结果 tmpAns。

// 遍历toDel，得到删除注释的中间结果
string tmpAns;
int last = 0;
for (auto p : toDel) {// 下标a和b-1之间的长度：b-atmpAns += combined.substr(last, p.first - last);last = p.second + 1;
}
// 分为toDel.size()+1段的最后一段
tmpAns += combined.substr(last, combined.length() - last);

Step4. 根据 \n 来分割 tmpAns 即可。

vector<string> ans;
int pos = tmpAns.find("\n", 0);
while (pos != string::npos) {if (pos != 0) {ans.push_back(tmpAns.substr(0, pos));}tmpAns.erase(0, pos+1);pos = tmpAns.find("\n", 0);
}

实现代码（C++）

class Solution {
public:vector<string> removeComments(vector<string>& source) {int state = 0;// 合并为一个字符串string combined;for (auto str : source) {combined += str + "\n";}vector<pair<int,int>> toDel;int len = combined.length();int cmtBegin = -1, cmtEnd = -1;for (int i = 0; i < len; i++) {char ch = combined[i];switch (state) {case 0:if (ch == '/') {state = 1;} else {state = 0;}break;case 1:if (ch == '/') { // 出现//，删去此行之后的内容// 找到从当前下标开始的第一个\n，下一次遍历从其之后开始int end = combined.find("\n", i);cmtBegin = i - 1;cmtEnd = end - 1;toDel.push_back({cmtBegin, cmtEnd});state = 0;i = end;} else if (ch == '*') { // 出现/*state = 2;cmtBegin = i - 1;} else {state = 0;}break;case 2:if (ch == '*') {state = 3;} else {state = 2;}break;case 3:if (ch == '/') { // cmtEndstate = 0;cmtEnd = i;toDel.push_back({cmtBegin, cmtEnd});} else { // 匹配*/失败，回退一位state = 2;i--;}break;} }// 遍历toDel，得到删除注释的中间结果string tmpAns;int last = 0;for (auto p : toDel) {tmpAns += combined.substr(last, p.first - last);last = p.second + 1;}tmpAns += combined.substr(last, combined.length() - last);// 根据\n分割vector<string> ans;int pos = tmpAns.find("\n", 0);while (pos != string::npos) {if (pos != 0) {ans.push_back(tmpAns.substr(0, pos));}tmpAns.erase(0, pos+1);pos = tmpAns.find("\n", 0);}return ans;}
};