LeetCode 917. Reverse Only Letters

Description

https://leetcode.com/problems/reverse-only-letters/

Given a string S, return the “reversed” string where all characters that are not a letter stay in the same place, and all letters reverse their positions.

Example 1:

Input: "ab-cd"
Output: "dc-ba"

Example 2:

Input: "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Example 3:

Input: "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"

Note:

  1. S.length <= 100
  2. 33 <= S[i].ASCIIcode <= 122 
  3. S doesn’t contain \ or "

Explanation

Two pointers technique to swap alphabetical letters.

Python Solution

class Solution:
    def reverseOnlyLetters(self, S: str) -> str:
        i = 0
        j = len(S) - 1
        
        S_list = list(S)
        
        while i < j:
            if S_list[i].isalpha() and S_list[j].isalpha():
                temp = S_list[j]
                S_list[j] = S_list[i]
                S_list[i] = temp
                
                i += 1
                j -= 1
            elif S_list[i].isalpha():
                j -= 1
            elif S_list[j].isalpha():
                i += 1
            else:
                i += 1
                j -= 1                
                
        return "".join(S_list)
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.