[LeetCode] Backspace String Compare (JAVA)

문제

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.

 

입출력 및 제약 사항

 

풀이

스택으로 풀 수 있는 문제였습니다. 각 문자열의 요소를 스택에 집어 넣되, '#'을 만났을 때는 빼 내면 됩니다. 이 문제에서 흥미로운 점은 Stack끼리 equals() 연산이 가능하다는 것입니다. Stack의 equals() 메소드를 살펴 보겠습니다.

 

Stack은 기본적으로 Vector의 상속을 받은 구조이고, Stack은 Vector의 equals()을 상속받습니다.

 

    public synchronized boolean equals(Object o) {
        return super.equals(o);
    }

 

또한, Vector는 AbstractList의 상속 받고 있고, 위 코드에서 볼 수 있듯이 equals() 메소드도 AbstractList로부터 온 것을 재활용하고 있습니다.

 

   public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof List))
            return false;

        ListIterator<E> e1 = listIterator();
        ListIterator<?> e2 = ((List<?>) o).listIterator();
        while (e1.hasNext() && e2.hasNext()) {
            E o1 = e1.next();
            Object o2 = e2.next();
            if (!(o1==null ? o2==null : o1.equals(o2)))
                return false;
        }
        return !(e1.hasNext() || e2.hasNext());
    }

 

위는 AbstractList의 equals() 메소드인데, Iterator를 사용하여 각 리스트의 요소를 비교하는 것을 알 수 있습니다. 즉, 정리하자면 두 Stack에 대해 equals() 연산을 수행하면, 각 Stack의 요소끼리 다시 equals() 연산으로 비교하고 모두 같다면 true를 반환합니다. 해당 문제는 Stack<Character>를 사용하므로 각 Stack의 문자가 '==' 연산으로 같으면 true입니다.

 

아래는 위 내용을 정리한 소스 코드입니다.

 

소스 코드

class Solution {
    public boolean backspaceCompare(String s, String t) {
        return backspaceString(s).equals(backspaceString(t));
    }
    
    private  Stack<Character> backspaceString(String str) {
        Stack<Character> stack = new Stack<>();
        for (char c : str.toCharArray()) {
            if ('#' != c) {
                stack.push(c);
                continue;
            }
            if (!stack.isEmpty()) {
                stack.pop();
            }
        }
        return stack;
    }
}