文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

数据结构与算法之比较含退格的字符串!

2024-12-02 12:23

关注

比较含退格的字符串

力扣题目链接:https://leetcode-cn.com/problems/backspace-string-compare

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

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

示例 1:

示例 2:

示例 3:

示例 4:

思路

本文将给出 空间复杂度的栈模拟方法 以及空间复杂度是的双指针方法。

普通方法(使用栈的思路)

这道题目一看就是要使用栈的节奏,这种匹配(消除)问题也是栈的擅长所在,跟着一起刷题的同学应该知道,在栈与队列:匹配问题都是栈的强项,我就已经提过了一次使用栈来做类似的事情了。

那么本题,确实可以使用栈的思路,但是没有必要使用栈,因为最后比较的时候还要比较栈里的元素,有点麻烦。

这里直接使用字符串string,来作为栈,末尾添加和弹出,string都有相应的接口,最后比较的时候,只要比较两个字符串就可以了,比比较栈里的元素方便一些。

代码如下:

  1. class Solution { 
  2. public
  3.     bool backspaceCompare(string S, string T) { 
  4.         string s; // 当栈来用 
  5.         string t; // 当栈来用 
  6.         for (int i = 0; i < S.size(); i++) { 
  7.             if (S[i] != '#') s += S[i]; 
  8.             else if (!s.empty()) { 
  9.                 s.pop_back(); 
  10.  
  11.         } 
  12.         for (int i = 0; i < T.size(); i++) { 
  13.             if (T[i] != '#') t += T[i]; 
  14.             else if (!t.empty()) { 
  15.                 t.pop_back(); 
  16.             } 
  17.         } 
  18.         if (s == t) return true; // 直接比较两个字符串是否相等,比用栈来比较方便多了 
  19.         return false
  20.     } 
  21. }; 

时间复杂度:,n为S的长度,m为T的长度 ,也可以理解是的时间复杂度

空间复杂度:当然以上代码,大家可以发现有重复的逻辑处理S,处理T,可以把这块公共逻辑抽离出来,代码精简如下:

  1. class Solution { 
  2. private: 
  3. string getString(const string& S) { 
  4.     string s; 
  5.     for (int i = 0; i < S.size(); i++) { 
  6.         if (S[i] != '#') s += S[i]; 
  7.         else if (!s.empty()) { 
  8.             s.pop_back(); 
  9.         } 
  10.     } 
  11.     return s; 
  12. public
  13.     bool backspaceCompare(string S, string T) { 
  14.         return getString(S) == getString(T); 
  15.     } 
  16. }; 

性能依然是:

优化方法(从后向前双指针)

当然还可以有使用 的空间复杂度来解决该问题。

同时从后向前遍历S和T(i初始为S末尾,j初始为T末尾),记录#的数量,模拟消除的操作,如果#用完了,就开始比较S[i]和S[j]。

动画如下:

如果S[i]和S[j]不相同返回false,如果有一个指针(i或者j)先走到的字符串头部位置,也返回false。

代码如下:

  1. class Solution { 
  2. public
  3.     bool backspaceCompare(string S, string T) { 
  4.         int sSkipNum = 0; // 记录S的#数量 
  5.         int tSkipNum = 0; // 记录T的#数量 
  6.         int i = S.size() - 1; 
  7.         int j = T.size() - 1; 
  8.         while (1) { 
  9.             while (i >= 0) { // 从后向前,消除S的# 
  10.                 if (S[i] == '#') sSkipNum++; 
  11.                 else { 
  12.                     if (sSkipNum > 0) sSkipNum--; 
  13.                     else break; 
  14.                 } 
  15.                 i--; 
  16.             } 
  17.             while (j >= 0) { // 从后向前,消除T的# 
  18.                 if (T[j] == '#') tSkipNum++; 
  19.                 else { 
  20.                     if (tSkipNum > 0) tSkipNum--; 
  21.                     else break; 
  22.                 } 
  23.                 j--; 
  24.             } 
  25.             // 后半部分#消除完了,接下来比较S[i] != T[j] 
  26.             if (i < 0 || j < 0) break; // S 或者T 遍历到头了 
  27.             if (S[i] != T[j]) return false
  28.             i--;j--; 
  29.         } 
  30.         // 说明S和T同时遍历完毕 
  31.         if (i == -1 && j == -1) return true
  32.         return false
  33.     } 
  34. }; 

其他语言版本

Java:

  1. // 普通方法(使用栈的思路) 
  2. class Solution { 
  3.     public boolean backspaceCompare(String s, String t) { 
  4.         StringBuilder ssb = new StringBuilder(); // 模拟栈 
  5.         StringBuilder tsb = new StringBuilder(); // 模拟栈 
  6.         // 分别处理两个 String 
  7.         for (char c : s.toCharArray()) { 
  8.             if (c != '#') { 
  9.                 ssb.append(c); // 模拟入栈 
  10.             } else if (ssb.length() > 0){ // 栈非空才能弹栈 
  11.                 ssb.deleteCharAt(ssb.length() - 1); // 模拟弹栈 
  12.             } 
  13.         } 
  14.         for (char c : t.toCharArray()) { 
  15.             if (c != '#') { 
  16.                 tsb.append(c); // 模拟入栈 
  17.             } else if (tsb.length() > 0){ // 栈非空才能弹栈 
  18.                 tsb.deleteCharAt(tsb.length() - 1); // 模拟弹栈 
  19.             } 
  20.         } 
  21.         return ssb.toString().equals(tsb.toString()); 
  22.     } 

python

  1. class Solution: 
  2.  
  3.     def get_string(self, s: str) -> str : 
  4.         bz = [] 
  5.         for i in range(len(s)) : 
  6.             c = s[i] 
  7.             if c != '#' : 
  8.                 bz.append(c) # 模拟入栈 
  9.             elif len(bz) > 0: # 栈非空才能弹栈 
  10.                 bz.pop() # 模拟弹栈 
  11.         return str(bz) 
  12.  
  13.     def backspaceCompare(self, s: str, t: str) -> bool: 
  14.         return self.get_string(s) == self.get_string(t) 
  15.         pass 

Go

  1. func getString(s string) string { 
  2.  bz := []rune{} 
  3.  for _, c := range s { 
  4.   if c != '#' { 
  5.    bz = append(bz, c); // 模拟入栈 
  6.   } else if len(bz) > 0 { // 栈非空才能弹栈 
  7.    bz = bz[:len(bz)-1] // 模拟弹栈 
  8.   } 
  9.  } 
  10.  return string(bz) 
  11.  
  12. func backspaceCompare(s string, t string) bool { 
  13.  return getString(s) == getString(t) 

 JavaScript

  1. // 双栈 
  2.  
  3. var backspaceCompare = function(s, t) { 
  4.  
  5. const arrS = [], arrT = []; // 数组作为栈使用 
  6.  
  7. for(let char of s){ 
  8.  
  9. char === '#' ? arrS.pop() : arrS.push(char); 
  10.  
  11.  
  12. for(let char of t){ 
  13.  
  14. char === '#' ? arrT.pop() : arrT.push(char); 
  15.  
  16.  
  17. return arrS.join('') === arrT.join(''); // 比较两个字符串是否相等 
  18.  
  19. }; 
  20.  
  21. //双栈精简 
  22.  
  23. var backspaceCompare = function(s, t) { 
  24.  
  25. const getString = s => { 
  26.  
  27. let arrS = []; 
  28.  
  29. for(let char of s){ 
  30.  
  31. char === '#' ? arrS.pop() : arrS.push(char); 
  32.  
  33.  
  34. return arrS.join(''); 
  35.  
  36.  
  37. return getString(s) === getString(t); 
  38.  
  39. }; 
  40.  
  41. //双指针 
  42.  
  43. var backspaceCompare = function(s, t) { 
  44.  
  45. let sSkipNum = 0; // 记录s的#数量 
  46.  
  47. let tSkipNum = 0; // 记录t的#数量 
  48.  
  49. let i = s.length - 1, j = t.length - 1; 
  50.  
  51. while(true) { 
  52.  
  53. while(i >= 0){ // 从后向前,消除s的# 
  54.  
  55. if(s[i] === '#') sSkipNum++; 
  56.  
  57. else { 
  58.  
  59. if (sSkipNum > 0) sSkipNum--; 
  60.  
  61. else break; 
  62.  
  63.  
  64. i--; 
  65.  
  66.  
  67. while (j >= 0) { // 从后向前,消除t的# 
  68.  
  69. if (t[j] === '#') tSkipNum++; 
  70.  
  71. else { 
  72.  
  73. if (tSkipNum > 0) tSkipNum--; 
  74.  
  75. else break; 
  76.  
  77.  
  78. j--; 
  79.  
  80.  
  81. // 后半部分#消除完了,接下来比较s[i] != t[j] 
  82.  
  83. if (i < 0 || j < 0) break; // s 或者t 遍历到头了 
  84.  
  85. if (s[i] !== t[j]) return false
  86.  
  87. i--;j--; 
  88.  
  89.  
  90. // 说明s和t同时遍历完毕 
  91.  
  92. if (i == -1 && j == -1) return true
  93.  
  94. return false
  95.  
  96. }; 

 

来源:今日头条内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯