力扣-844题比较含退格的字符串（C++）- 栈+双指针

布满荆棘的人生 2022-08-29 15:50 106阅读 0赞

题目链接：[https://leetcode-cn.com/problems/backspace-string-compare/][https_leetcode-cn.com_problems_backspace-string-compare]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]  
思路一：栈

class Solution {
        
    public:
        stack<char> intostk(string str){
        
            stack<char> stk;
            for(auto e:str){
        
                if(e=='#'&&!stk.empty()) stk.pop();
                else if(e!='#'){
        stk.push(e);cout<<e<<' ';}//注意："a####c"的情况
            }
            cout<<endl;
            return stk;
        }
    
        bool backspaceCompare(string s, string t) {
        
            stack<char> stk1=intostk(s);
            stack<char> stk2=intostk(t);
    
            while(!stk1.empty()&&!stk2.empty()){
        
                if(stk1.top()==stk2.top()){
        
                    stk1.pop();
                    stk2.pop();
                }else{
        
                    return false;
                }
            }
    
            if(!stk1.empty()||!stk2.empty()) return false;
            else return true;
        }
    };

思路二：双指针

class Solution {
        
    public:
    
        string deal(string str){
        
            if(str=="") return str;
            int showindex=0;
    
            for(int fastindex=0;fastindex<str.size();fastindex++){
        
                if(str[fastindex]!='#') str[showindex++]=str[fastindex];
                else showindex--;
                if(showindex<0) showindex=0;
            }
    
            return str.substr(0,showindex);
        }
    
        bool backspaceCompare(string s, string t) {
        
            cout<<deal(s)<<endl;
            cout<<deal(t)<<endl;
    
            return deal(s)==deal(t);
        }
    };

解法三：双指针

class Solution {
        
    public:
        bool backspaceCompare(string s, string t) {
        
            int j=0;
            for(int i=0;i<s.size();i++){
        
                if(s[i]!='#') s[j++]=s[i];
                else {
        
                    j--;
                    if(j<0) j=0;
                }
            }
    
            int k=0;
            for(int i=0;i<t.size();i++){
        
                if(t[i]!='#') t[k++]=t[i];
                else {
        
                    k--;
                    if(k<0) k=0;
                }
            }
    
            if(k!=j) return false;
            else if(s.substr(0,j)==t.substr(0,k)) return true;
            else return false;
        }
    };

[https_leetcode-cn.com_problems_backspace-string-compare]: https://leetcode-cn.com/problems/backspace-string-compare/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20220829/9ed2b16e234a45a59bdd5ef5ea8c2690.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]: /images/20220829/f4769d9feb25416ebd0df479e54d8b9c.png