P2501. 敏感字段加密

解题思路

题目概述

本题为纯模拟题。简单理解题意就是，把下划线 `_` 作为分隔符对原字符串进行分割（如果产生空字符串则跳过），将分割后索引为 K（索引从 0 记起）的字符串修改为 ******。

关键难点

题意中比较难理解的一句话是：

> 可以通过两个双引号 "" 来标识包含下划线 _ 的命令字或空命令字（仅包含两个双引号的命令字），双引号不会在命令字内部出现

这句话的意思是，如果某一个下划线 `_` 出现在一对引号内，那么这个下划线不作为分隔符使用。这一点也导致我们不能够直接使用 split() 来处理原字符串，而是需要在一个 for 循环 中来进行字符串的分割。

模拟过程

1. 设置标志位

由于需要考虑某段字符串是否位于一对引号内，我们可以设置一个标志 flag：

• 当 flag 为 True 时，说明此时位于一对引号内
• 当 flag 为 False 时，说明此时不位于一对引号内

初始化这个 flag 为 False，并在循环过程中反复切换 flag。

2. 初始化结果列表

构建一个初始化列表 lst = [""]，包含一个空串。lst 用于储存最终的分割结果。

3. 遍历字符串

遍历原字符串 s 中的字符 ch，分情况讨论：

• `ch` 是非引号且非下划线：直接延长进 lst 中的最后一个字符串 lst[-1] 即可
• `ch` 是引号：需要将 ch 延长进 lst[-1]，同时修改 flag = not flag，因为接下来的字符是否位于一对引号中的状态切换了
• `ch` 是下划线：还需要判断当前 flag 的值：
• 若 flag = True：说明此时的下划线位于一对引号中，不作为分隔符使用。下划线的行为和普通字母或数字没有区别，直接延长进 lst[-1]
• 若 flag = False：说明此时下划线作为分隔符使用。此时 lst 中的最后一个字符串将不再延长，后续的字符串会另起一个新的字符串，因此我们在 lst 末尾加入一个新的空串 ""，来储存后续的字符

4. 去除空串

遍历结束后，由于原字符串 s 中可能存在一些连续的下划线 _，lst 中可能会存在一些空串，我们需要对这些空串进行去重操作。直接使用以下代码即可完成：

5. 输出结果

最终，我们选择答案列表 ans 中的第 K 个元素，将其修改为 ****** 后并输出。注意此处还需要判断 ans 的长度，如果小于等于 K 的话，说明索引 K 越界，输出 ERROR。

复杂度分析 设 L 为输入字符串 s 的长度（题目约定不超过 127 字节）。

• 时间复杂度：O(L)。整个算法对 s 只做一次遍历，每个字符按「双引号 / 下划线 / 其他字符」三种情况之一处理，各是常数代价：要么追加到当前命令字末尾，要么翻转标志 Flag，要么在 lst 末尾新开一个空串。遍历结束后过滤空串得到 ans、替换第 idx 个命令字、再用下划线 join 拼接输出，这些步骤处理的字符总量也不超过 L 加上常数长度的“******”，同样是线性代价。
• 空间复杂度：O(L)。lst 与 ans 中所有命令字的字符总数不超过 L；此外只有 Flag、idx 等常数个变量。