917. Reverse Only Letters

題目敘述

Given a string s, reverse the string according to the following rules:

• All the characters that are not English letters remain in the same position.
• All the English letters (lowercase or uppercase) should be reversed.

Return s after reversing it.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= s.length <= 100
• s consists of characters with ASCII values in the range [33, 122].
• s does not contain '\"' or '\\'.

Hint 1:

This problem is exactly like reversing a normal string except that there are certain characters that we have to simply skip. That should be easy enough to do if you know how to reverse a string using the two-pointer approach.

題目翻譯

有一個參數 s，需要將此字串的英文字母都反轉。但是其中非英文字母的 char 保持在原位置。

解法解析

這題有兩種解法，第一種解法是使用 Stack 的資料結構，第二種是使用反轉指標的方式。這兩種作法的 Time complexity 和 Space complexity 都是 O(n)。在作法上個人喜歡第一種方式，比較好閱讀。 還要注意的是有些程式語言例如 python 有提供方便的 sugar function isalpha 可以快速分辨是否為英文字母，但有些沒有。所以統一的作法可以使用 Regex 或是比較 char 的 ASCII，如題目中 Constraints 的第二個限制所提示的。 因為 Stack 的資料結構是所謂的 FILO，所以剛好可以做到反轉的。

1. 第一步先過濾非字母的符號，儲存在 stack 中
2. 遍歷 s
3. 每個 char 是判斷是不是字母，如果是就從步驟一中儲存的 stack pop 出最後一筆、如果不是就直接儲存該 char
4. 最後將所有的 char 合成

程式範例

Python

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

JavaScript

/**
 * @param {string} s
 * @return {string}
 */
var reverseOnlyLetters = function (s) {
    const letters = s.split('').filter((v) => /[a-zA-Z]/.test(v));

    const ans = [];
    for (let i of s) {
        if (/[a-zA-Z]/.test(i)) {
            ans.push(letters.pop());
        } else {
            ans.push(i);
        }
    }
    return ans.join('');
};

Go

import "strings"

func isLetter(b byte) bool {
    return (b >= 'a' && b <= 'z') || (b >= 'A' && b <= 'Z')
}

func reverseOnlyLetters(s string) string {
    letters := []byte{}
    for i := range s {
        if isLetter(s[i]) {
            letters = append([]byte{s[i]}, letters...)
        }
    }
    var res strings.Builder
    j := 0
    for i := range s {
        if !isLetter(s[i]) {
            res.WriteByte(s[i])
        } else {
            res.WriteByte(letters[j])
            j++
        }
    }
    return res.String()
}

Swift

class Solution {
    func reverseOnlyLetters(_ S: String) -> String {
        let arr = Array(S)
        var letters = arr.filter({ $0.isLetter })
        var result = [Character]()
        for s in arr {
            result.append(s.isLetter ? letters.removeLast() : s)
        }
        return String(result)
    }
}

Kotlin

class Solution {
    fun reverseOnlyLetters(s: String): String {
        val sarr = s.toCharArray()
        val m = s.length
        val st = ArrayDeque<Char>()
        val queue = ArrayDeque<Int>()

        for (i in 0 until m) {
            val ch = sarr[i]
            if (ch.isLetter()) {
                st.push(ch)
            } else {
                queue.offer(i)
            }
        }

        var idx = 0
        val sb = StringBuilder()

        while (idx < m) {
            if (!queue.isEmpty() && queue.peek() == idx) {
                sb.append(s[queue.poll()])
            } else {
                if (!st.isEmpty()) {
                    sb.append(st.pop())
                }
            }
            idx++
        }

        return sb.toString()
    }
}