題目敘述
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 <= 100s 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，所以剛好可以做到反轉的。
- 第一步先過濾非字母的符號，儲存在 stack 中
- 遍歷
s
- 每個 char 是判斷是不是字母，如果是就從步驟一中儲存的 stack pop 出最後一筆、如果不是就直接儲存該 char
- 最後將所有的 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
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()
}
}