正文

返回 导航

LeetCode算法第844. Backspace String Compare

发布日期:2019-11-02 12:00:01

LeetCode算法第844. Backspace String Compare

技术提高是一个循序渐进的过程,所以我讲的leetcode算法题从最简单的level开始写的,然后> 到中级难度,最后到hard难度全部完。目前我选择C语言,Python和Java作为实现语言,因为这三种语言还是比较典型的。由于篇幅和> 精力有限,其他语言的实现有兴趣的朋友请自己尝试。初级难度说的差不多的时候,我打算再加点其他内容,我可能会从操作系统到协议栈,从分布式> 聊到大数据框架,从大数据聊到人工智能,... ...。

如果有任何问题可以在文章后评论或者私信给我。

我会持续分享下去,敬请您的关注。

LeetCode 844. 比较含退格的字符串(Backspace String Compare)

问题描述:

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

  1. 1 <= S.length <= 200;
  2. 1 <= T.length <= 200;
  3. S 和 T 只含有小写字母以及字符 '#'。

示例:

LeetCode算法第844. Backspace String Compare

C语言实现:

有两种方式可以解这道题。这两种方式都跟遍历字符串的方向有关。

第一种:顺序重左到右遍历S和T:

考虑到“#”的行为:每遇到一个“#”就删除前一个已经遍历的字符。

所以这是完全满足栈的行为:

  • 为S和T分别建立一个长度和字符串长度一样的栈;
  • 如果当前遍历的字符不是“#”,压入栈中;
  • 如果当前遍历的字符是“#”,栈顶即是前一个字符,弹出;
  • 如此下去,直到S和T都遍历完;

然后依次开始弹出两个栈中的元素,同时比较每次弹出的两个字符是否相等,如果有不等的情况就返回false。

第二种:逆序从右向左遍历S和T:

注意观察。'#'只会对左边的元素有影响,对右边的元素没有影响。

因此我们可以从右向左同时遍历S和T遍历:

  • 如果当前遍历的字符是“#”,就统计当前字符串中“#”出现的次数,继续遍历下一个字符;
  • 如果当前遍历的字符不是“#”,且当前统计的“#”出现的次数大于0,就说明当前的字符应该被忽略,继续下一个;
  • 如果当前遍历的字符不是“#”,且当前统计的“#”出现的次数等于0,就说明当前的字符是最终要出现与另一个字符串做比较的字符,暂时跳出遍历

对S和T都做这样的遍历,如果它们都暂时性调出遍历,这时候会分别得到两个不会被“#”删除的字符。

然后比较它们,如果不同,就直接返回false。否则继续上面的遍历,一直到其中的一个字符串遍历结束。

我们比较这两种算法。

时间复杂度方面:

都是O(len(S)+len(T))。实际情况,第二种算法时间复杂度可能要好一些,因为对于结果是false的case,不需要遍历完两个字符串。

空间复杂度方面:

第一种算法,要维护两个栈长度是,空间复杂度是O(len(S)+len(T));

第二种算法,不需要任何空间存放字符,空间复杂度是O(1);

终上所述,第二种算法要更好些。我们的实现也是第二种,第一种算法相对更简单,读者可以自行尝试。

具体代码如下:

LeetCode算法第844. Backspace String Compare

我的这个算法,代码不太友好,因为返回不是在函数的最后,我是为了让代码更短些,实践中不建议大家这么干。

我们应该定义一个变量来存放返回值,保证返回值在函数的最后返回。

另外对于第一层的死循环,注意这里不会真的死掉。之所以要用死循环,是为了保证遍历和比较能不断的进行下去。最后S和T一定至少会有一个遍历完的,那个时候函数一定会返回。

LeetCode算法第844. Backspace String Compare

Java语言实现:

Java 的实现和C语言的实现一致,不再撰述。代码如下:

LeetCode算法第844. Backspace String Compare

LeetCode算法第844. Backspace String Compare

Python语言实现:

Python 的实现和C语言的实现一致,不再撰述。代码如下:

LeetCode算法第844. Backspace String Compare

LeetCode算法第844. Backspace String Compare


谢谢大家一直以来的关注和支持!

我一直在努力的写好每一篇文章,画好每一份插图。但是作为一个996从业人员,时间精力十分有限。所以针对评论部分,以后只回答粉丝的问题和私信。希望仅仅是路过的朋友能够体谅,希望更多人关注《吾是我师》,谢谢!


点击阅读全文

猜你喜欢