[LeetCode] Backspace String Compare (JAVA)

[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 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를 사용하므로 각 Stack의 문자가 '==' 연산으로 같으면 true입니다.

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

소스 코드

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

from http://steady-coding.tistory.com/499 by ccl(A) rewrite - 2021-11-10 13:27:25