算法日常・每日刷题--＜栈＞2

844. 比较含退格的字符串 - 力扣LeetCode844. 比较含退格的字符串 - 给定 s 和 t 两个字符串当它们分别被输入到空白的文本编辑器后如果两者相等返回 true 。# 代表退格字符。注意如果对空文本输入退格字符文本继续为空。 示例 1输入s ab#c, t ad#c输出true解释s 和 t 都会变成 ac。示例 2输入s ab##, t c#d#输出true解释s 和 t 都会变成 。示例 3输入s a#c, t b输出false解释s 会变成 c但 t 仍然是 b。 提示 * 1 s.length, t.length 200 * s 和 t 只含有小写字母以及字符 # 进阶 * 你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗https://leetcode.cn/problems/backspace-string-compare/题目描述给定字符串s和t#代表退格字符。模拟编辑器输入效果遇到#删除前一个字符空文本执行退格不产生任何变化。处理完毕后判断两个字符串最终结果是否一致。示例 1s ab#c , t ad#c→ 处理后均为ac返回true示例 2s ab## , t c#d#→ 处理后均为空串返回true示例 3s a#c , t b→cvsb返回false解法使用字符串模拟栈遍历字符普通字符直接追加到栈末尾遇到#栈非空则弹出末尾字符退格栈为空直接忽略分别处理 s、t 得到最终字符串直接对比是否相等。class Solution { public: bool backspaceCompare(string s, string t) { string ret1; for(auto ch :s) { if(ret1.size()1ch#) ret1.pop_back(); else if(ch#) ; else ret1ch; } string ret2; for(auto ch :t) { if(ret2.size()1ch#) ret2.pop_back(); else if(ch#) ; else ret2ch; } if(ret1ret2) return true; else return false; } };