[c++][leetcode] Backspace String Compare :: seoftware

 

#은 앞에 문자를 지우는 역할이다. #이 자기 역할을 모두 수행하고 난 후의 문자열을 비교하는 문제

 

---

 

소스코드

---

 

 

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        stack<char> s_st, t_st;
        for(int i = 0; i < S.length(); i++){
            if(S[i] != '#') s_st.push(S[i]);
            else if(!s_st.empty()){
                s_st.pop();
            }
        }
        for(int i = 0; i < T.length(); i++){
            if(T[i] != '#') t_st.push(T[i]);
            else if(!t_st.empty()){
                t_st.pop();
            }
        }
        if(s_st.empty() && t_st.empty()) return true;
        else{
            while(!s_st.empty() || !t_st.empty()){
                if(s_st.empty() || t_st.empty()) return false;
                if(s_st.top() != t_st.top()) return false;
                s_st.pop(); t_st.pop();
            }
        }
        return true;
    }
};

 

1. 스택을 이용해서 풀었다.

 

2. S와 T 각각 문자면 stack에 넣고, #이면 앞에 문자를 하나씩 지웠다(stack이 비지 않았을 때만). 

 

3. 두 스택에서 하나씩 꺼내가며 # 처리된 후 두 문자열이 같은지 비교를 했다.