leetcode题 844. 比较含退格的字符串(解法一：用双指针)

本文主要是介绍leetcode题 844. 比较含退格的字符串(解法一：用双指针)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

思路：一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。

具体地，我们定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符：

若该字符为退格符，则我们需要多删除一个普通字符，我们让 skip 加 1；

若该字符为普通字符：

若 skip 为 0，则说明当前字符不需要删去；

若 skip 不为 0，则说明当前字符需要删去，我们让 skip 减 1。

这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。

class Solution {
    public boolean backspaceCompare(String s, String t) {
                int i = s.length() - 1; int j = t.length() - 1;
                int skipi = 0; int skipt = 0;

                while(i >= 0 || j >= 0){
                    while(i >= 0){
                        if(s.charAt(i) == '#'){
                            skipi++;
                            i--;
                        }else if(skipi > 0){
                            skipi--;
                            i--;
                        }else{
                            break;
                        }
                    }

                    while(j >= 0){
                        if(t.charAt(j) == '#'){
                            skipt++;
                            j--;
                        }else if(skipt > 0){
                            skipt--;
                            j--;
                        }else{
                            break;
                        }
                    }
                if(i >= 0 && j >= 0){
                     if(s.charAt(i) != t.charAt(j)){
                      return false;
                    }
                }else if(i >= 0 || j>= 0){
                       return false;
                   }     
                     i--;
                     j--;
               
               
                }
                return true;

    }
}

这篇关于leetcode题 844. 比较含退格的字符串(解法一：用双指针)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！