What is the time complexity of the Reverse Prefix of Word problem?

The time complexity is O(n), where n is the length of the string 'word'. This is because we scan the string once to locate the target character and reverse the necessary part of the string.

How do you handle the case when the character does not exist in the string?

If the target character is not found in the string, the function returns the string unchanged, without performing any reversal.

What is the space complexity of this solution?

The space complexity is O(n), as a new string is generated to hold the result after reversal. The solution operates in-place for the reversal step.

Can the Reverse Prefix of Word problem be solved without using extra space?

Yes, the solution can be optimized to work in-place by performing the reversal directly on the original string or its representation.

How can two-pointer scanning help in solving the Reverse Prefix of Word problem?

Two-pointer scanning allows you to efficiently locate the first occurrence of the target character and reverse the required portion of the string with minimal overhead.

#2000

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

反转单词前缀

给你一个下标从 0 开始的字符串 word 和一个字符 ch 。找出 ch 第一次出现的下标 i ，反转 word 中从下标 0 开始、直到下标 i 结束（含下标 i ）的那段字符。如果 word 中不存在字符 ch ，则无需进行任何操作。例如，如果 word = "abcdefd" 且 ch …

双指针字符串栈

题目描述

给你一个下标从 0 开始的字符串 word 和一个字符 ch 。找出 ch 第一次出现的下标 i ，反转 word 中从下标 0 开始、直到下标 i 结束（含下标 i ）的那段字符。如果 word 中不存在字符 ch ，则无需进行任何操作。

例如，如果 word = "abcdefd" 且 ch = 'd' ，那么你应该反转从下标 0 开始、直到下标 3 结束（含下标 3 ）。结果字符串将会是 "dcbaefd" 。

返回 结果字符串 。

示例 1：

输入：word = "abcdefd", ch = 'd'
输出："dcbaefd"
解释："d" 第一次出现在下标 3 。 
反转从下标 0 到下标 3（含下标 3）的这段字符，结果字符串是 "dcbaefd" 。

示例 2：

输入：word = "xyxzxe", ch = 'z'
输出："zxyxxe"
解释："z" 第一次也是唯一一次出现是在下标 3 。
反转从下标 0 到下标 3（含下标 3）的这段字符，结果字符串是 "zxyxxe" 。

示例 3：

输入：word = "abcd", ch = 'z'
输出："abcd"
解释："z" 不存在于 word 中。
无需执行反转操作，结果字符串是 "abcd" 。

提示：

1 <= word.length <= 250
word 由小写英文字母组成
ch 是一个小写英文字母

lightbulb

解题思路

方法一：模拟

我们先找到字符 $ch$ 第一次出现的下标 $i$ ，然后反转从下标 $0$ 开始、直到下标 $i$ 结束（含下标 $i$ ）的那段字符，最后将反转后的字符串与下标 $i + 1$ 开始的字符串拼接即可。

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

1

2

3

4

5

class Solution:
    def reversePrefix(self, word: str, ch: str) -> str:
        i = word.find(ch)
        return word if i == -1 else word[i::-1] + word[i + 1 :]

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Candidate can quickly identify the problem's two-pointer scanning approach.
question_mark
Candidate efficiently handles cases where the target character does not exist in the string.
question_mark
Candidate implements the in-place reversal technique without using unnecessary extra space.

warning

常见陷阱

外企场景

error
Failing to handle the case where the target character does not exist in the string.
error
Not reversing the string in place, leading to extra space usage.
error
Overcomplicating the solution by using additional data structures instead of two-pointer scanning.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider handling multiple occurrences of the target character and reversing up to the last occurrence.
arrow_right_alt
Extend the problem by allowing the user to reverse the segment up to a specified index instead of just the first occurrence.
arrow_right_alt
Consider reversing substrings from any starting index to a given character index.

help

常见问题

外企场景

继续练习

#1963 使字符串平衡的最小交换次数 #2019 解出数学表达式的学生分数 #2030 含特定字母的最小子序列