[LeetCode/Easy] 844. Backspace String Compare

1. Input

1) 문자열 s

2) 문자열 t

 

2. Output

1) 문자열을 규칙에 따라 정리한 후 s와 t가 같다면 true를, 다르면 false를 반환

- 규칙: 문자열에 ‘#’이 있다면 앞 글자를 지운다. 키보드의 backspace 역할을 하는 것이다. 만약 ‘#’ 앞이 빈 문자열이라면 아무 일도 일어나지 않는다.

 

3. Constraint

1) 1 <= s.length, t.length <= 200

2) s와 t는 영어 소문자와 ‘#’로만 이루어져 있다.

 

4. Example

Input: s = "ab#c", t = "ad#c" -> Output: true (“ac”==“ac”)

Input: s = "a#c", t = "b" -> Output: false (“c”!=“b”)

 

5. Code

1) 첫 코드(2022/12/29)

import java.util.*;

Stack ss = new Stack();
Stack tt = new Stack();

for(int i=0 ; i<s.length() ; i++){
    if(s.charAt(i)=='#'){
        if(!ss.empty()) ss.pop();
    } else
        ss.push(s.charAt(i));
}

for(int i=0 ; i<t.length() ; i++){
    if(t.charAt(i)=='#'){
        if(!tt.empty()) tt.pop();
    } else
        tt.push(t.charAt(i));
}
 
boolean answer = true;
if(ss.size()!=tt.size()) answer = false;
else{
    while(!ss.empty() && !tt.empty()){
        if(ss.pop()!=tt.pop()){
            answer = false; break;
        }
    }
}
return answer;

  - 꽤 괜찮은 성능을 보였다.

  - O(n) time, O(1) space로 푸는 방법은 잘 모르겠다.