Python으로 푸는 LeetCode 917. Reverse Only Letters (Easy)

알파벳이 아닌 문자(-,!,? 등등)를 제외한 알파벳 문자를 뒤집어서 반환하는 코드를 짜시오.

LeetCode에서 푼 문제 리스트 보기

LeetCode에서 문제 보기

Github에서 코드 보기

문제 풀이

문제를 푸는 방법은 다양하다. 처음 풀었던 방식은 문자열의 맨앞(start_index)와 맨뒤(last_index)의  index를 하나하나 확인하면서 앞뒤 모두 알파벳 문자열인 경우에만 두 자리를 바꿔주는 방법이다.

방법 1. 포인터를 이동하며 문자열 교환

만약 알파벳이 아니라면 index를 낮추거나 높여서 가리키고 있는 index를 문자열의 가운데로 점점 이동하며 문자열을 바꿔준다. start_index와 last_index가 서로 만나면 문자열 교환을 중지하고 str()으로 변환하여 결과값을 반환한다.

방법 2. Stack을 이용

LeetCode의 Solution에 있던 방법으로 내가 생각하지 못한 방법이기 때문에 기록해 둔다.

문자열을 순회하며 알파벳인 경우에만 따로 stack에 담아둔다. 다시 문자열을 처음부터 순회하면서 알파벳인 경우에는 stack에서 원소를 꺼내 결과값에 추가하고, 알파벳이 아니면 해당 문자를 결과값에 추가한다. 시간 복잡도나 공간 복잡도의 측면에서 O(N) 만큼이 소요된다.

파이썬 코드 - 방법 1 (포인터 이동)

class Solution:
    def reverseOnlyLetters(self, S: str) -> str:
        """
        Runtime : faster than 92.02% of Python3
        Memory Usage : less than 5.56% of Python3
        """
        start_index = 0
        last_index = (len(S) - 1)
 
        if len(S) <= 1:
            return S
 
        S = list(S)
        while start_index < last_index:
 
            sv = S[start_index]
            lv = S[last_index]
 
            if not lv.isalpha():
                last_index -= 1
                continue
 
            if not sv.isalpha():
                start_index += 1
                continue
 
            S[start_index], S[last_index] = S[last_index], S[start_index]
            start_index += 1
            last_index -= 1
 
        return ''.join(S)

파이썬 코드 - 방법2 (Stack 이용)

class Solution:
    def reverseOnlyLetters(self, S: str) -> str:
        stack = []
        for s in S:
            if s.isalpha():
                stack.append(s)
        result = ''
        for s in S:
            if s.isalpha():
                result += stack.pop()
            else:
                result += s
        return result