What is the best approach to solve the 'Reverse Only Letters' problem?

The two-pointer approach is ideal. It allows for efficient string manipulation by skipping non-letter characters while reversing only the alphabetic ones.

Why do we need to reverse only the letters in the string?

The problem specifies that we must reverse only the alphabetic characters while keeping all other characters, such as punctuation and digits, in their original positions.

How can I optimize my solution for the 'Reverse Only Letters' problem?

Using a two-pointer approach ensures an optimal time complexity of O(N) as it processes each character only once. No extra space is needed besides the string itself.

What are the edge cases I need to consider for 'Reverse Only Letters'?

Consider cases like an empty string, strings with no letters, or strings that are already reversed. Ensure that non-alphabetic characters are unaffected.

How does GhostInterview help with solving the 'Reverse Only Letters' problem?

GhostInterview guides you step-by-step through the problem, providing real-time feedback on common mistakes, offering hints, and ensuring your solution is both efficient and correct.

#917

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

仅仅反转字母

给你一个字符串 s ，根据下述规则反转字符串：所有非英文字母保留在原有位置。所有英文字母（小写或大写）位置反转。返回反转后的 s 。示例 1：输入： s = "ab-cd" 输出： "dc-ba" 示例 2：输入： s = "a-bC-dEf-ghIj" 输出： "j-Ih-gfE-dC…

双指针字符串

题目描述

给你一个字符串 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 不含 '\"' 或 '\\'

lightbulb

解题思路

方法一：双指针

我们用两个指针 $i$ 和 $j$ 分别指向字符串的头部和尾部。当 $i < j$ 时，我们不断地移动 $i$ 和 $j$ ，直到 $i$ 指向一个英文字母，并且 $j$ 指向一个英文字母，然后交换 $s[i]$ 和 $s[j]$ 。最后返回字符串即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        cs = list(s)
        i, j = 0, len(cs) - 1
        while i < j:
            while i < j and not cs[i].isalpha():
                i += 1
            while i < j and not cs[j].isalpha():
                j -= 1
            if i < j:
                cs[i], cs[j] = cs[j], cs[i]
                i, j = i + 1, j - 1
        return "".join(cs)

speed

复杂度分析

指标	值
时间	O(N)
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
The candidate should clearly demonstrate an understanding of two-pointer techniques and its application to string manipulation.
question_mark
Look for clarity in handling edge cases, such as strings with no alphabetic characters or strings where all characters are letters.
question_mark
The candidate should be comfortable with explaining their thought process, particularly around skipping non-alphabetic characters while ensuring the overall time complexity is linear.

warning

常见陷阱

外企场景

error
Failing to handle edge cases like an empty string or a string with no alphabetic characters.
error
Not accounting for the fact that only letters need to be reversed, and other characters should remain in their original positions.
error
Overcomplicating the solution by using additional data structures when a simple in-place swap suffices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Reverse a string while only skipping digits.
arrow_right_alt
Modify the problem to handle uppercase and lowercase letters differently.
arrow_right_alt
Add more non-alphabetic characters like symbols, ensuring they remain in place during the reversal.

help

常见问题

外企场景

继续练习

#925 长按键入 #942 增减字符串匹配 #844 比较含退格的字符串