leetcode 844, Backspace String Compare

문제 설명

문자열이 주어지는데, 이때 '#'부분은 backspace이다. 이때 두 문자열이 같으면 true, 다르면 false를 반환하는 문제다.

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

Backspace String Compare - LeetCode

문제 풀이

stack

처음에는 단순 문자열 문제인 줄 알았지만, '#'이 연달아 나오는 예제를 보고 stack이라고 생각했다. 

 

풀이 자체는 상당히 단순한데, 문자를 하나씩 탐색하다가 '#'이 나오면 stack에서 하나 pop을 한다. 이때 주의해야 할 점은 stack이 비었는지를 확인하는 것. 만일 문자가 '#'인데 stack이 비어 있다면 아무런 행위도 하지 않는다. 그리고 그냥 문자가 나온다면 stack에 push를 해주면 된다.

 

그리고 stack에 남은 값들을 하나씩 빼서 StringBuilder를 이용해 붙여주면 된다.

twopointer

투 포인터로 푸는 방법도 있길래 공유를 하자면, 만일 문자가 '#'이 아니라면 s[k]에는 현재 문자를 넣어주고 k는 ++를 한다. 그리고 이때 문자가 '#'이면 k를 한 칸 뒤로 물려준다. 이때 조심해야 할 것은 '#'이 맨 첫번째 나오는 경우. 그렇기에 max(k-1, 0)을 통해서 k가 0인 경우에는 0을 반환하도록 한다.

코드

java

import java.util.*;

class Solution {

    public String deleteBackspace(String s) {
        Stack<Character> stack = new Stack<>();

        for (int i=0; i<s.length(); i++) {
            if (s.charAt(i) == '#' && !stack.isEmpty()) {
                stack.pop();
                continue;
            } else if (s.charAt(i) == '#' && stack.isEmpty()) {
                continue;
            }
            stack.push(s.charAt(i));
        }

        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        return sb.toString();
    }

    public boolean backspaceCompare(String s, String t) {
        //System.out.println(deleteBackspace(s));
        //System.out.println(deleteBackspace(t));

        return deleteBackspace(s).equals(deleteBackspace(t));
    }
}

python

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        
        def usingTwoPointers(s):
            k=0
            for i in range(len(s)):
                if s[i] != '#':
                    s[k] = s[i]
                    k++
                else:
                    # 0번째에 #이 오면 이것도 처리해줘야 한다
                    # k-1을 해서 직전의 값을 덮어씌우는 방식
                    k = max(k-1, 0)
            return k

        def deleteBackspace(s):
            stack = []
            string = ""

            for i in range(len(s)):
                if s[i] == '#' and len(stack) != 0:
                    stack.pop()
                    continue;
                elif s[i] == '#' and len(stack) == 0:
                    continue;
                stack.append(s[i])
            
            string = ''.join(s for s in stack)
            return string

        return deleteBackspace(s) == deleteBackspace(t)