这道题可以用stack，从左到右扫字符串，遇到backspace就pop，最后比较两个stack里的字符即可。但问题是如果string非常长的话会耗过多的空间。但是如果我们从右向左的话，如果有backspace我们就可以跳过当前字符继续匹配，这样的话我们就不需要存额外的东西。具体的算法就是我们统计当前有的backspace的数量，如果为正的话我们就跳过当前的字符继续匹配，直到发现不匹配或者匹配完为止。这里不匹配有三种情况：
- T和S某处字符不匹配
- T匹配完，但是S剩下的不全是backspace
- S匹配完，但是T剩下不全是backspace
时间复杂度O(N)，常数空间，代码如下：
No comments:
Post a Comment