P2605. 密码输入检测

解题思路

本题分为两个步骤：

1. 对输入的密码进行退格处理，这显然可以使用栈来完成。 2. 对处理完毕之后的密码进行各个条件的判断，直接调用各种字符串相关的 API 即可完成。

与本题在栈上应用非常类似的题目，还有 经典题型. 比较含退格的字符串。

易错点

退格操作逻辑关系不清晰

关于操作退格，后续代码我是这样完成的：

也可以写成这样：

上述代码的含义是，先判断当前字符是否为 "<"，若：

• 字符不是 "<"，则直接是一个有效的字符，进入栈中
• 字符是 "<"，则仍需判断 stack 是否为空栈，若：
• stack 不是空栈，则需要进行退格操作，删除栈顶元素
• stack 是空栈，则无需进行任何操作，因为已经没有任何元素可以被删除了

上述逻辑其实是非常简单和清晰的。但是有一些同学会写成这样的代码：

或者

出现这样错误的问题在于，对各个条件的逻辑关系并没有想清楚。

ch != "<" 和 ch == "<"，这两个条件是互斥关系。换句话说，一个字符 ch 要么是 "<"，要么是除了 "<" 以外的其他字符。

ch != "<" 和 ch == "<" and len(stack) > 0，这两个条件并不是互斥关系。除了两种情况之外，还有一种可能是 ch == "<" and len(stack) == 0。

以上述第二份错误代码为例，之所以出现这样的错误，是因为认为除了 ch == "<" and len(stack) > 0 以外，写在 else 中的剩余所有情况都是 ch != "<" 的情况。

但其实不然，else 中还包括了 ch == "<" and len(stack) == 0 的情况。当 ch 为 "<" 且栈为空的情况出现的时候，按照代码逻辑会将退格符号 "<" 加入栈中，这显然是不正确的。

非字符串 API 写法

特别注意，有些同学觉得字符串中关于判断是否为数字、大小写字母、空格等 API 感觉较难记忆。我们也并非一定要使用 API，而使用更加简单的比较符（大于小于等于）即可完成该题。即：

复杂度分析 设输入字符流的长度为 n。第一步退格处理是对 s 的单次遍历：普通字符入栈，退格符 < 在栈非空时弹出栈顶，单步 O(1)，整趟 O(n)；处理后栈中元素个数不超过 n，join 拼接出 s_new 也是 O(n)。第二步合法性检查对 s_new 做了五次独立扫描：长度判断 O(1)，四个 any 分别检查是否含大写字母、小写字母、数字、特殊字符，每个最坏扫完整个 s_new，各为 O(n)，且 any 找到第一个满足条件的字符就会短路提前结束。常数遍的线性扫描加起来仍是 O(n)。因此总时间复杂度 O(n)，没有嵌套循环，瓶颈只是对字符串的几遍线性扫描。空间复杂度 O(n)：栈与拼接出的 s_new 在最坏情况（输入中没有退格符）下都与输入等长。