[LeetCode/C++] 844. Backspace String Compare

pictrue of leetcode problem 844

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        string a = "";
        string b = "";
        
        for(int i = 0; i < s.length(); i++) {
            if(!a.empty() && s[i] == '#') a.pop_back();
            if(s[i] != '#') a.push_back(s[i]);
        }
        for(int j = 0; j < t.length(); j++) {
            if(!b.empty() && t[j] == '#') b.pop_back();
            if(t[j] != '#') b.push_back(t[j]);
        }
        return a.compare(b) == 0 ? true : false;
    }
};

---

이 문제는 #이 뒤로가기 버튼이라고 생각했을 때 s라는 문장과 t라는 문장이 같은 문장인지를 O(N) 시간 복잡도로 풀어내는 문제였습니다.

 

뒤로가기를 생각했을 때 가장 최근에 쌓인 문자열을 지우게 되므로 Stack으로 풀 수 있다고 생각하였고 스택과 같은 역할을 하는 stirng 문자열 자체를 push/pop하며 풀어내야겠다고 생각하였습니다.

 

비어있지 않고 #이 들어온다면 가장 최근 문자열을 pop하고 그렇지 않다면 push하는 형태로 구현하였습니다.

for문 1개에서 두 문자열을 모두 처리하고 싶었으나 실력이 부족해서 구현하지 못하였고 문자열을 push / pop하지 않고 index로 접근한다면 memory 부분에서 더 좋은 효율을 낼 수 있었을텐데 하는 아쉬움이 남은 문제였습니다.

---

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

Backspace String Compare - LeetCode