iT邦幫忙

2021 iThome 鐵人賽

DAY 14
1
自我挑戰組

每日LeetCode解題紀錄系列 第 14

LeetCode解題 Day14

917. Reverse Only Letters

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


題目解釋

你會能到一個字串s ,請按照下列規則並回傳反轉的字串

  • 所有的非英文字元要留在原本位置
  • 所有的英文字母要反轉

example

https://i.imgur.com/ugUgcHQ.png


解法

這題只要知道哪個字元是英文字母和要轉去哪而已

比較常見的方法有兩種:

1. Two pointer

前後都個放一個指標,一個由前往後、另一個由後往前

就樣就能馬上知道前面的字母要放到哪個位置了

class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        
        ans = [i for i in s]
        p = 0
        q = len(s) - 1
        
        while p < q:
            
            if ans[p].isalpha() and ans[q].isalpha():
                ans[p], ans[q] = ans[q], ans[p] #swap
                p += 1
                q -= 1
            
            elif not ans[p].isalpha():
                p += 1 
            
            elif not ans[q].isalpha():
                q -=1
                
        return ''.join(ans)

2. Stack

先把所有英文字母用堆疊存起來,而堆疊取出的方式是後進先出,也就是取出的過程正好就是反轉的順序

class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        
        letter = [i for i in s if i.isalpha()]
        
        ans = []
        
        for i in s:
            if i.isalpha():
                ans.append(letter.pop())
            else:
                ans.append(i)
        
        return ''.join(ans)

閒聊

過兩週了 耶!


上一篇
LeetCode解題 Day13
下一篇
LeetCode解題 Day15
系列文
每日LeetCode解題紀錄30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言