[LeetCode] 844. Backspace String Compare

https://leetcode.com/problems/backspace-string-compare/

Backspace String Compare - LeetCode

Backspace String Compare

 

 

두 스트링 s와 t가 주어졌을때, s와 t가 같은지 출력하는 문제이다.

이때 #은 backspace를 의미한다.

 

#을 어떻게 처리하느냐가 관건인데,

stack을 사용하면 편리하다.

stack<char>를 생성하여 알파벳을 하나씩 넣다가 #을 만나게 되면 pop으로 하나를 꺼내주면 된다.

모두 넣었다면 빈 스트링에 스택에 있는 것을 하나씩 꺼내 더해주면 된다.

같은 문자열이라면 역순도 같으므로 역순으로 쌓여도 상관 없다.

 

전체 풀이 코드

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        stack<char> st;
        string strs[2] = {s,t};
        for (int i=0; i<2; i++) {
            for (int j=0; j<strs[i].size(); j++) {
                if (strs[i][j]!='#') st.push(strs[i][j]);
                else if (!st.empty()) st.pop();
            }
            strs[i] = "";
            while (!st.empty()) {
                strs[i]+=st.top();
                st.pop();
            }
        }
        return strs[0] == strs[1];
    }
};