[leetCode] Java - Backspace String Compare

30일 챌린지 9일 차 문제입니다.

 

Backspace String Compare

 

- 문제 : 

- 풀이 :

 

class Solution {
    public boolean backspaceCompare(String S, String T) {
        return convert(S).equals(convert(T));
    }
    
    public String convert(String text) {
		int count = 0;
		StringBuilder new_text = new StringBuilder();
		for(int i=text.length()-1; i>=0; i--) {
			if(text.charAt(i) == '#') {
				count++;
			}else {
				if(count > 0) {
					count--;
				}else {
					new_text.append(text.charAt(i));
				}
			}
			
		}
		return new_text.toString();
	}
}

#이 있으면 다음 문자는 백스페이스로 지우는 문제입니다.

 

count로 #의 개수를 확인하고 count 만큼 해당 문자를 건너뛰는 방식으로 구현했습니다.

문자는 String 그대로 붙이면 시간 복잡도가 높아지기 때문에 StringBuilder를 사용하여 append 했습니다.

문자 비교는 앞뒤가 상관없기 때문에 뒤에서 시작했지만 순차적으로 추가하고 마지막에 String으로 변화했습니다.

 

그래서 실제적으로 두 개의 문자열이 같은지 확인하는 방식입니다.

 

시간 복잡도는 두개의 문자열을 해당 문자열의 길이만큼 for을 돌기 때문에 최대 O(N)입니다.

N은 두 개의 문자열의 길이만큼입니다.