844. Backspace String Compare

EASY

 

문제

---

Backspace String Compare  - LeetCode

​

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

 

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 "".

Example 3:

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

​

---

내 풀이

class Solution {
    public boolean backspaceCompare(String s, String t) {
        if (erase(s).equals(erase(t))) {
            return true;
        }
        return false;
    }

    public String erase(String st) {
        String res = "";
        int count = 0;
        for (int i=st.length()-1; i>=0; i--) {
            if (st.charAt(i) == '#') {
                count ++;
            } else if (count != 0) {
                count--;
            } else {
                res += st.charAt(i);
            }
        }
        return res;
    }
}

 

Runtime

5ms

Memory

41.96MB

​

풀이는 다음과 같다

​

String의 가장 마지막에서부터 하나씩 탐색

#일 경우 count ++;

#이 아닐 경우 count 확인해서 0일 때는 res에 추가

0보다 클 때에는 count 줄이고 넘어감

​

---

 

참고할 만한 풀이

class Solution {
    public boolean backspaceCompare(String s, String t) {
        Stack<Character> stack1= new Stack();
        Stack<Character> stack2= new Stack();
        
        int n1=0,n2=0;
        while(n1<s.length()){
            if(s.charAt(n1)=='#' ){
                if(!stack1.empty()){
                    stack1.pop();
                }
            }
            else{
                stack1.push(s.charAt(n1));
            }
            n1++;
        }
        while(n2<t.length() ){
            if(t.charAt(n2)=='#'){
                if(!stack2.empty()){
                    stack2.pop();
                }
            }
            else{
                stack2.push(t.charAt(n2));
            }
            n2++;
        }
        while(!stack1.empty() && !stack2.empty() && stack1.peek()==stack2.peek()){
            stack1.pop();
            stack2.pop();
        }
        if(!stack1.empty() || !stack2.empty()){
            return false;
        }
        return true;
        
    }
}

 

Stack을 사용한 풀이

​

Stack의 성질은 다음과 같다.

1. 후입선출 (LIFO : Last In First Out) 구조로 나중에 들어온 데이터 먼저 빠져나감

2. 깊이 우선 탐색(DFS)에 주로 이용됨

​

Stack<Integer> st = new Stack<>();

// 추가 add, push
st.add(1); // 1 추가 - stack에는 1
st.push(2); // 2 추가 - stack에는 1, 2

// 마지막 요소 확인 peek
st.peek(); // 마지막 요소인 2 return됨 - stack에는 1,2
// 빈 stack에 peek 할 경우 NoSuchElementException 발생

// 제거 pop
st.pop(); // 2 제거 - stack에는 1
// 빈 stack에 pop 할 경우 EmptyStackException 발생

// 값 전부 제거 clear
st.clear(); // 값 전부 제거 - stack에 아무것도 없음

// empty, isEmpty
st.empty(); // st가 비었는지 확인 (boolean)
st.isEmpty(); // empty와 동일

// 값의 위치 찾기
st.search(1); // 1이 return됨, 중복 인자 있을 경우 마지막 위치 반환
// 찾는 값이 없을 경우 -1 return