c++ - Backspace String 比较给定两个字符串 s 和 t，如果相等则返回 true

Question

我使用堆栈的这个测试用例出现运行时错误

 "bxj##tw", "bxj###tw"

Line 171: Char 16: runtime error: reference binding to misaligned address 0xbebebebebebec0ba for type 'int', which requires 4 byte alignment (stl_deque.h)
0xbebebebebebec0ba: note: pointer points here
<memory cannot be printed>
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_deque.h:180:16

class Solution {

public:
    bool backspaceCompare(string s, string t) {

        stack<int>st1;
        stack<int>st2;
        
        for(int i=0; i<s.size(); i++){

            if(st1.empty() && s[i]!='#'){

                st1.push(s[i]);
            }
            else{
                if(!st1.empty() && s[i]=='#'){

                    st1.pop();
                }
                else if(s[i]=='#' && (st1.empty())){

                    continue;
                }
                else{
                    st1.push(s[i]);
                }
            }
        }
        for(int i=0; i < t.size(); i++){

            if(st2.empty() && t[i]!='#'){

                st2.push(t[i]);
            }
            else{
                if(!st2.empty() && t[i]=='#'){

                    st2.pop();
                }
                else if(t[i]=='#' && st2.empty()){

                    continue;
                }
                else{

                    st2.push(t[i]);
                }
            }
        }
        if(st1.empty() && st2.empty()){

            return "";
        }
        while(!st1.empty()){

            if(st1.top()!= st2.top()){

                return false;
            }

            else{

                st1.pop();

                st2.pop();
            }
        }

        return true;
    }
};

标签： c++stringstack

Answer 1

我不会使用 a stack<char>，因为自然表示是 a string，并且您没有使用任何stack能够在前面扩展或收缩的功能（除了您可以说的末尾return a == b）。string有push_back和pop_back方法也是如此。

对于较小的输入（例如针对此挑战问题所保证的输入），我建议构建两个“编辑器”并与以下内容进行比较==：

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        return backspace(s) == backspace(t);
    }

private:
    string backspace(const string &s) {
        string editor = "";
        string::const_iterator commandItr = s.cbegin();
        while(commandItr != s.cend())
            if(*commandItr == '#' && !editor.empty()) {
                editor.pop_back();
                ++commandItr;
            } else if(*commandItr != '#')
                editor.push_back(*commandItr++);
            else
                ++commandItr;
        
        return editor;
    }
};

然而，他们确实挑战了编码器使用 O(1) 内存。这是一个例子：

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int left = s.size() - 1;
        int right = t.size() - 1;
        while(true) {
            left = backspace(s, left);
            right = backspace(t, right);
            
            if (left == -1 && right == -1)
                return true;
            if (left == -1 && right != -1 || right == -1 && left != -1)
                return false;
            if(s[left--] != t[right--])
                return false;
        }
    }
private:
    // Returns first index from back that indexes to a non-deleted character
    int backspace(string const &s, int startingIndex) {       
        if(startingIndex == -1)
            return -1;
        
        if(s[startingIndex] != '#')
            return startingIndex;
        
        unsigned backspaceCount = 0;
        while(true) {
            while(startingIndex != -1 && s[startingIndex] == '#') {
                ++backspaceCount;
                --startingIndex;
            }

            while (startingIndex != -1 && backspaceCount && s[startingIndex] != '#') {
                --startingIndex;
                --backspaceCount;
            }
            
            if (startingIndex == -1)
                return -1;
            else if(s[startingIndex] != '#' && !backspaceCount)
                return startingIndex;
        }
    }
};