LeetCode 力扣官方题解 | 917. 仅仅反转字母
917.仅仅反转字母（点击文末阅读原文查看题目）
题目描述
给你一个字符串 s ，根据下述规则反转字符串：
所有非英文字母保留在原有位置。
所有英文字母（小写或大写）位置反转。
返回反转后的 s。
示例 1：
输入：s = "ab-cd"输出："dc-ba"
示例 2：
输入：s = "a-bC-dEf-ghIj"输出："j-Ih-gfE-dCba"
示例 3：
输入：s = "Test1ng-Leet=code-Q!"输出："Qedo1ct-eeLg=ntse-T!"
提示：
1 <= s.length <= 100
s 仅由 ASCII 值在范围 [33, 122] 的字符组成
s 不含 '\"' 或 '\\'
解决方案
方法一：双指针
思路
我们使用 left 指针从左边开始扫描字符串 s，right 指针从右边开始扫描字符串 s。如果两个指针都扫描到字母，且 left < right，那么交换 s[left] 和 s[right]，然后继续进行扫描；否则表明反转过程结束，返回处理后的字符串。
Python3
class Solution:def reverseOnlyLetters(self, s: str) -> str:ans = list(s)left, right = 0, len(ans) - 1while True:while left < right and not ans[left].isalpha(): # 判断左边是否扫描到字母left += 1while right > left and not ans[right].isalpha(): # 判断右边是否扫描到字母right -= 1if left >= right:breakans[left], ans[right] = ans[right], ans[left]left += 1right -= 1return ''.join(ans)
C++
class Solution {public:string reverseOnlyLetters(string s) {int n = s.size();int left = 0, right = n - 1;while (true) {while (left < right && !isalpha(s[left])) { // 判断左边是否扫描到字母left++;}while (right > left && !isalpha(s[right])) { // 判断右边是否扫描到字母right--;}if (left >= right) {break;}swap(s[left], s[right]);left++;right--;}return s;}};
Java
class Solution {public String reverseOnlyLetters(String s) {int n = s.length();char[] arr = s.toCharArray();int left = 0, right = n - 1;while (true) {while (left < right && !Character.isLetter(s.charAt(left))) { // 判断左边是否扫描到字母left++;}while (right > left && !Character.isLetter(s.charAt(right))) { // 判断右边是否扫描到字母right--;}if (left >= right) {break;}swap(arr, left, right);left++;right--;}return new String(arr);}public void swap(char[] arr, int left, int right) {char temp = arr[left];arr[left] = arr[right];arr[right] = temp;}}
C#
public class Solution {public string ReverseOnlyLetters(string s) {int n = s.Length;char[] arr = s.ToCharArray();int left = 0, right = n - 1;while (true) {while (left < right && !char.IsLetter(s[left])) { // 判断左边是否扫描到字母left++;}while (right > left && !char.IsLetter(s[right])) { // 判断右边是否扫描到字母right--;}if (left >= right) {break;}Swap(arr, left, right);left++;right--;}return new String(arr);}public void Swap(char[] arr, int left, int right) {char temp = arr[left];arr[left] = arr[right];arr[right] = temp;}}
C
static inline void swap(char *c1, char *c2) {char tmp = *c1;*c1 = *c2;*c2 = tmp;}char *reverseOnlyLetters(char *s){int n = strlen(s);int left = 0, right = n - 1;while (true) {while (left < right && !isalpha(s[left])) { // 判断左边是否扫描到字母left++;}while (right > left && !isalpha(s[right])) { // 判断右边是否扫描到字母right--;}if (left >= right) {break;}swap(s + left, s + right);left++;right--;}return s;}
Golang
func reverseOnlyLetters(s string) string {ans := []byte(s)left, right := 0, len(s)-1for {for left < right && !unicode.IsLetter(rune(s[left])) { // 判断左边是否扫描到字母left++}for right > left && !unicode.IsLetter(rune(s[right])) { // 判断右边是否扫描到字母right--}if left >= right {break}ans[left], ans[right] = ans[right], ans[left]left++right--}return string(ans)}
JavaScript
var reverseOnlyLetters = function(s) {const n = s.length;const arr = [...s];let left = 0, right = n - 1;while (true) {while (left < right && !(/^[a-zA-Z]+$/.test(s[left]))) { // 判断左边是否扫描到字母left++;}while (right > left && !(/^[a-zA-Z]+$/.test(s[right]))) { // 判断右边是否扫描到字母right--;}if (left >= right) {break;}swap(arr, left, right);left++;right--;}return arr.join('');};const swap = (arr, left, right) => {const temp = arr[left];arr[left] = arr[right];arr[right] = temp;}
复杂度分析
时间复杂度：O(n)，其中 n 是字符串 s 的长度。反转过程需要 O(n)，C 语言计算字符串长度需要 O(n)。
空间复杂度：O(1) 或 O(n)。某些语言字符串不可变，需要 O(n) 的额外空间。
BY /
本文作者：力扣
编辑&版式：Irene
声明：本文归“力扣”版权所有，如需转载请联系。
点个在看，少个 bug
微信扫码关注该文公众号作者
戳这里提交新闻线索和高质量文章给我们。
来源: qq
点击查看作者最近其他文章