[Leetcode/TwoPointer] 844. Backspace String Compare

Two Pointers Approach (O(n) 시간, O(1) 공간)

• 뒤에서부터 문자열을 처리하면서 '#'을 만나면 백스페이스를 적용한다.
• 각 문자열에 대해 유효한 문자 위치를 찾아 비교한다.
• 포인터를 이동하면서 문자 비교를 진행한다.

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        # 두 개의 포인터를 각각 문자열 s와 t의 끝에서 시작
        i, j = len(s) - 1, len(t) - 1  
        # 백스페이스('#')의 개수를 추적하는 변수
        back_s, back_t = 0, 0  

        # 두 문자열 중 하나라도 아직 탐색할 문자가 남아있는 동안 반복
        while i >= 0 or j >= 0:
            # 문자열 s에서 유효한 문자를 찾는 과정
            while i >= 0:
                if s[i] == "#":  # 백스페이스를 만나면
                    back_s += 1  # 백스페이스 개수 증가
                    i -= 1  # 다음 문자로 이동
                elif back_s > 0:  # 백스페이스가 남아있다면 (즉, 다른 #이 더 있을 경우)
                    back_s -= 1  # 해당 문자 삭제 처리
                    i -= 1  # 다음 문자로 이동
                else:  
                    break  # 유효한 문자 발견 시 중단

            # 문자열 t에서 유효한 문자를 찾는 과정
            while j >= 0:
                if t[j] == "#":  # 백스페이스를 만나면
                    back_t += 1  # 백스페이스 개수 증가
                    j -= 1  # 다음 문자로 이동
                elif back_t > 0:  # 백스페이스가 남아있다면
                    back_t -= 1  # 해당 문자 삭제 처리
                    j -= 1  # 다음 문자로 이동
                else:  
                    break  # 유효한 문자 발견 시 중단

            # 유효한 문자 위치에서 비교 (둘 다 유효한 문자일 때)
            if i >= 0 and j >= 0 and s[i] != t[j]:
                return False  # 서로 다르면 False 반환
            
            # 한쪽 문자열이 먼저 끝난 경우(False)
            if (i >= 0) != (j >= 0):
                return False  

            # 다음 문자 비교를 위해 포인터 이동
            i -= 1
            j -= 1

        # 모든 문자가 동일하면 True 반환
        return True

코드 흐름 정리

1. 문자열 끝에서 시작하는 두 개의 포인터 사용 (i, j)
   • s와 t의 마지막 문자부터 비교해 나간다.
2. 백스페이스 처리
   • #을 만나면 백스페이스 개수를 증가 (back_s, back_t).
   • # 개수가 남아 있으면 현재 문자를 무시하고 지나감.
3. 문자 비교
   • 백스페이스가 적용된 후의 문자가 다르면 False 반환.
   • 한쪽 문자열이 먼저 끝나면 False 반환.
4. 반복하며 모든 문자 처리 후 True 반환
   • 끝까지 모든 문자가 동일하면 True 반환.

시간 및 공간 복잡도

• 시간 복잡도: O(n)
  → 모든 문자를 한 번씩 탐색하므로 선형 시간에 해결.
• 공간 복잡도: O(1)
  → 추가 메모리를 사용하지 않고 포인터만 사용.