[Leetcode] 844. Backspace String Compare 문제풀이

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

Backspace String Compare - LeetCode

 

문제 내용

문자열 2개에 backspace(문자 1개 지우는 키)가 포함된 문자열로 주어진다.

문자열 2개의 최종 결과값이 같은지 비교하는 문제

Example 1:
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Example 2:
Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

 

문제 풀이

시간복잡도가 O(n)이고 공간복잡도가 O(1) 으로 풀 수가 있다.

 

backspace의 특징은 이전 문자를 지우는 것이다.

그래서 문자열 비교할때 뒤에서 부터 비교하면된다.

backspace가 나오면 그 만큼 더 가면 된다.

 

class Solution {
public:
    int getCharIndex(string& s, int e) {
        int bs = 0;
        for (int i = e; i >= 0; --i) {
            if (s[i] == '#')
                ++bs;
            else if (bs == 0)
                return i;
            else
                --bs;
        }
        return -1;
    }
    bool backspaceCompare(string s, string t) {
        int i = s.length()-1;
        int j = t.length()-1;
        while(i >= 0 && j >= 0) {
            int si = getCharIndex(s, i);
            int tj = getCharIndex(t, j);
            
            if (si == -1 && tj == -1)
                return true;
            
            if (si == -1 || tj == -1)
                return false;
            if (s[si] != t[tj])
                return false;
            
            i = si-1;
            j = tj-1;
        }
        
        if (i != -1)
            i = getCharIndex(s, i);
        if (j != -1)
            j = getCharIndex(t, j);

        return i == -1 && j == -1;
    }
};