当前位置 博文首页 > Jealyn的个人博客:LeetCode 844题 比较含退格的字符串 -- JavaS
给定?S
?和?T
?两个字符串,当它们分别被输入到空白的文本编辑器后,判断二者是否相等,并返回结果。?#
?代表退格字符。
输入:S = "ab#c", T = "ad#c" 输出:true 解释:S 和 T 都会变成 "ac"。
输入:S = "ab##", T = "c#d#" 输出:true 解释:S 和 T 都会变成 ""。
输入:S = "a##c", T = "#a#c" 输出:true 解释:S 和 T 都会变成 "c"。
输入:S = "a#c", T = "b" 输出:false 解释:S 会变成 "c",但 T 仍然是 "b"。
提示:
1 <= S.length <= 200
1 <= T.length <= 200
S
?和?T
?只含有小写字母以及字符 '#'。方法分析:
这道题目只要弄清了题意,就很简单。?
#
?代表退格字符,其会将它前面的那个字符在字符串中清除掉,当然,该字符本身也不会出现在结果之中。例如,对于字符串"a#b"得到的结果就为"b";对于字符串"#ab#c"得到的结果就为"ac"。而且要注意到,每一次的操作都将直接对原字符串进行修改。代码实现:
var backspaceCompare = function(S, T) { return backspace(S) == backspace(T); }; function backspace(str) { let backspaceStr = ''; for(let i = 0;i < str.length;i++) { backspaceStr = str[i] != "#" ? backspaceStr + str[i] : backspaceStr.slice(0,-1); } return backspaceStr; }
代码解析:
在backspaceCompare函数内部,我们分别调用backspace函数来对两者执行退格处理。因为S和T的处理方式一致,故我们把它封装为一个函数,从而减少代码量和提高复用度。
在backspace函数内,我们对字符串进行遍历。如果当前字符不是#的话,就将其输出到结果字符串中,否则就删除结果字符串的最后一个字符,也就是删除掉原字符串中#前面的那个字符,最后返回结果字符串即可。
该算法的时间复杂度为,其中n为字符串的长度
该算法的空间复杂度为。
参考链接:https://leetcode-cn.com/problems/backspace-string-compare/description/
cs下一篇:没有了