844. 比较含退格的字符串

844. 比较含退格的字符串

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

思路

第一个很容易想到栈，直接用str模拟栈操作即可。第二个考虑到使用O（1）的空间复杂度，#退格字符只与前面字符有关，可以从后遍历，计算#字符的个数，面对一个#字符时，增加一个删除字母个数，面对一个非#字符时，减少一次删除字母个数，直到遍历到头或者碰见一个字母但删除字母个数为0时，就可以比较两个字符串的该字母是否相等，依次遍历即可。

代码

class Solution { public: bool backspaceCompare(string S, string T) { int s_len = S.size() - 1, t_len = T.size() - 1; int skip_s = 0, skip_t = 0; while(s_len >= 0 || t_len >= 0) { //后序遍历s字符串 while(s_len >= 0) { if(S[s_len] == '#') { skip_s++; s_len--; } else if(skip_s > 0){ skip_s--; s_len--; } else { break; } } //同理 while(t_len >= 0) { if(T[t_len] == '#') { skip_t++; t_len--; } else if(skip_t > 0) { skip_t--; t_len--; } else { break; } } //比较字母 if(s_len >= 0 && t_len >= 0) { if(S[s_len] != T[t_len]) { return false; } } else { if(s_len >= 0 || t_len >= 0) { return false; } } s_len--; t_len--; } return true; } };