【Leetcode每日一题】844. 比较含退格的字符串|重构字符串/双指针

系统管理员 2023-09-23 23:10 30阅读 0赞

![在这里插入图片描述][b88c49c5b7e04dacaaed7cf2fc928687.gif_pic_center]

>  *  **博主简介：努力学习的预备程序媛一枚~**
>  *  **博主主页： [@是瑶瑶子啦][Link 1]**
>  *  **所属专栏: [LeetCode每日一题–进击大厂][LeetCode]**

# 前言： #

昨天的[【Leetcode每日一题】27. 原地移除元素|神级理解双指针][Leetcode_27.]一文中，生动形象的为大家讲解如何理解双指针，受到了很好的反馈，今天趁热打铁，瑶瑶子为大家带来一道双指针的plus版本题目，会比昨天的难一点，但是本质和逻辑是一样的（就是两个人干活，男女搭配，干活不累！）  
在讲今天这道题目之前，推荐大家去做一下力扣283题目，这里给出链接和我的题解，和昨天27题非常类似，只有细小差别。  
[283. 移动零][283.]

> 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。  
> 请注意 ，必须在不复制数组的情况下原地对数组进行操作。

class Solution1 {
        
        public void moveZeroes(int[] nums) {
        
            int quickIndex = 0;//快指针，用于遍历
            int slowIndex = 0;//慢指针用于挖坑
            for (; quickIndex < nums.length; quickIndex++) {
        
                if (nums[quickIndex] == 0) {
        
                    continue;//遇见0就跳过
                }
                nums[slowIndex++] = nums[quickIndex];//慢指针在挖坑，等待快指针给过来的"萝卜"
            }
            for (; slowIndex < nums.length; slowIndex++)//慢指针把0填上去
            {
        
                nums[slowIndex] = 0;
            }
        }
    }

### 目录 ###

*  前言：
 *  题目描述
 *  题目分析
 *   *  方法1：
     *  方法2

# 题目描述 #

链接:[844. 比较含退格的字符串][844.]

> 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。\# 代表退格字符。  
> 注意：如果对空文本输入退格字符，文本继续为空。

> 可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？  
> (O(1)的复杂度会用**方法2**实现)

# 题目分析 #

## 方法1： ##

最容易想到的方法，也就是为两个字符串分别重写构造各自的新字符串，来存储删除后的两个新字符串。再把两个新字符串进行比较（**非原地修改**)

*  **设计一个方法，用于获取修改后的新字符串**
 *  **将两者对应删除空格后的新字符串进行比较**

本质还是昨天所说的双指针，一个遍历，一个指向待插入位置（但是其实双指针我觉得，在这题当中，不是形式上的双指针，而是思想上的，需要体会，逻辑是完全一样

class Solution {
        
        public boolean backspaceCompare(String s, String t) {
        
            return newString(s).equals(newString(t));
        }
        //通过这个函数，得到退格后的新字符串（不含#的字符串）
        public String newString(String str) {
        
            StringBuffer ans = new StringBuffer();
            for (int i = 0; i < str.length(); i++) {
        
                if (str.charAt(i) != '#') {
        
                    ans.append(str.charAt(i));//填入
                } else {
        
                    if (ans.length() > 0) {
        
                        ans.deleteCharAt(ans.length() - 1);//慢指针遇到#，就把萝卜拔掉，不前行
                    }
                }
            }
            return ans.toString();//将StringBuffer类型转换为String类型返回
        }
    }

本质是快慢指针法，在newString这个方法中对一个字符串的操作中体现体现

*  时间复杂度O(N+M)
 *  空间复杂度O(N+M)

## 方法2 ##

也是双指针，与方法1以及之前所讲的双指针不同的是：**快慢两个指针作用在同一个字符串/数组上；而纯双指针，即两个指针分工明确，各不相同，作用在不同的字符串上/数组。**

具体用代码来体现（瑶瑶子附有有保姆级详细注释）

class Solution {
        
        public boolean backspaceCompare(String s, String t) {
        
            int pointerS = s.length() - 1;//指针1号指向s字符串中的待比较元素
            int pointerT = t.length() - 1;//指针2号指向t字符串中的待比较元素
            while (pointerS >= 0 || pointerT >= 0) {
        //注意这里是||，为什么不是&&？举例：hhh 和 空，结果还是false
                //求出s字符串中第一个待比较元素
                int skipS = 0;
                int slipT = 0;
                while (pointerS >= 0) {
        
                    if (s.charAt(pointerS) == '#') {
        
                        skipS++;
                        pointerS--;//向后遍历下一个元素
                    } else if (skipS > 0) {
        //类似于“出栈”过程，出栈之前必须判断栈是否为空！
                        pointerS--;
                        skipS--;
                    } else {
        //即skipS=0,元素不为'#'的情况-->找到待比较元素
                        break;//跳出循环
                    }
                }
                //同样的方法，找到t字符串中待比较元素
                while (pointerT >= 0) {
        
                    if (t.charAt(pointerT) == '#') {
        
                        slipT++;
                        pointerT--;
                    } else if (slipT > 0) {
        
                        pointerT--;
                        slipT--;
                    } else {
        
                        break;
                    }
                }
                //比较两个循环中分别出来的字符
                if (pointerS >= 0 && pointerT >= 0) {
        
                    if (s.charAt(pointerS) != t.charAt(pointerT)) {
        
                        return false;
                    }
                } else {
        
                    if (pointerS >= 0 || pointerT >= 0)//一个字符串还存在字符待比较，另一个一个字符串的字符已经比较完：如：a null
                        return false;
                }
    
                //指针后退，为下一次比较做准备
                pointerS--;
                pointerT--;
            }
            //大循环跳出，说明两者皆为空字符串，返回true
            return true;
        }
    }

**易错点**

*  1：超出时间限制：每次循环比较字符后，没有让指针后退`pointerS--;pointerT--`
 *  2：指针越界异常（java.lang.StringIndexOutOfBoundsException: String index out of range: -1）：在循环内，并不能保证pointerS和ponterT大于0，所以在进行`charAt(pointerS)/charAt(pointerT)`运算时，必须保证此时下标大于or等于0(`if (pointerS >= 0 && pointerT >= 0)`)

**方法2反思：**  
 双指针思想主要体现在pointerS和pointerB经过一些**巧妙的处理`while循环`,指向各自字符串的待比较元素，并分别比较。**  
**【重点】**除了双指针思想；此题方法2：不得不学习的重点：  
**1. 对于删除空格，采用从后往前遍历方式  
2. 巧妙利用计数器（skipS&skipT)，记录指针所需要跳过的字符个数**

--------------------

> **write in the end:  
> 后续还会更新很多双指针题目来加深对双指针的理解！以及持续更新Java和刷题系列文章。还不快快关注！\[笔芯\]**
> 
>  *  **专栏系列文章：  
>     [【Leetcode每日一题】27. 原地移除元素|神级理解双指针][Leetcode_27.]  
>     [【Leetcode每日一题】69. x 的平方根/Sqrt(x)|二分查找][Leetcode_69. x _Sqrt_x]  
>     [【Leetcode每日一题】34.在排序数组中查找元素的第一个和最后一 个位置|二分求下标][Leetcode_34._]**
>  *  **建立此专栏的初衷是为了监督自己每天认真刷一个题，积少成多。并把自己每次刷题的思路、收获以博文的形式分享出来，帮助更多人，以及方便后续复习。如果有兴趣的同学可以订阅此专栏，我们一起刷题，一起交流，进步和学习！**[专栏：LeetCode每日一题–进击大厂][LeetCode 1]

![在这里插入图片描述][456fe14b32044d3083bc25853cf0ced7.gif_pic_center]

[b88c49c5b7e04dacaaed7cf2fc928687.gif_pic_center]: https://img-blog.csdnimg.cn/b88c49c5b7e04dacaaed7cf2fc928687.gif#pic_center
[Link 1]: https://blog.csdn.net/Yaoyao2024?spm=1011.2559.3001.5343
[LeetCode]: https://blog.csdn.net/yaoyao2024/category_12115665.html?spm=1001.2014.3001.5482
[Leetcode_27.]: https://blog.csdn.net/Yaoyao2024/article/details/128776141?spm=1001.2014.3001.5501
[283.]: https://leetcode.cn/problems/move-zeroes/
[844.]: https://leetcode.cn/problems/backspace-string-compare/
[Leetcode_69. x _Sqrt_x]: https://blog.csdn.net/Yaoyao2024/article/details/128762817?spm=1001.2014.3001.5501
[Leetcode_34._]: https://blog.csdn.net/Yaoyao2024/article/details/128758800?spm=1001.2014.3001.5501
[LeetCode 1]: https://blog.csdn.net/yaoyao2024/category_12115665.html
[456fe14b32044d3083bc25853cf0ced7.gif_pic_center]: https://img-blog.csdnimg.cn/456fe14b32044d3083bc25853cf0ced7.gif#pic_center