# LeetCode Solution, Easy, 917. Reverse Only Letters

# [917. Reverse Only Letters](https://leetcode.com/problems/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

```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

```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

```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

```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

```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()
    }
}
```