反转单词前缀

难度: Easy

给你一个下标从 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 是一个小写英文字母

Submission

运行时间: 22 ms

内存: 16.1 MB

class Solution:
    def reversePrefix(self, word: str, ch: str) -> str:
        n = len(word)
        word = list(word)

        l = r = 0
        while r < n and word[r] != ch:
            r += 1

        if r < n:
            while l < r:
                word[l], word[r] = word[r], word[l]
                l += 1
                r -= 1
        return ''.join(word)

Explain

解题思路：首先将输入的字符串转换为字符列表，以便进行原地修改。接着使用两个指针l（左指针）和r（右指针）来查找字符ch的第一次出现位置。l初始化为0，r从0开始向右移动，直到找到字符ch或者遍历完整个字符串。如果在字符串中找到了字符ch，则进行反转操作。具体的反转操作是通过'while l < r'循环进行的，在循环中交换l和r指向的字符，然后l向右移动一位，r向左移动一位，直至l不再小于r。最后，将字符列表转回字符串形式返回。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def reversePrefix(self, word: str, ch: str) -> str:
        n = len(word)  # 获取字符串长度
        word = list(word)  # 将字符串转换为字符列表以便原地修改

        l = r = 0  # 初始化左右指针
        while r < n and word[r] != ch:  # 寻找字符ch的位置
            r += 1

        if r < n:  # 如果找到字符ch
            while l < r:  # 反转从索引0到索引r的部分
                word[l], word[r] = word[r], word[l]  # 交换l和r位置的字符
                l += 1  # 移动左指针
                r -= 1  # 移动右指针
        return ''.join(word)  # 将字符列表重新转换为字符串并返回

Explore

在Python中，字符串是不可变的数据类型，这意味着无法直接修改字符串中的单个字符。因此，要实现原地修改的效果，必须先将字符串转换为可变的数据结构，如字符列表。这样可以在列表中直接进行字符的交换，操作完成后再将列表转换回字符串。这种方法相比于每次修改都生成新的字符串，可以节省内存消耗，并可能提高执行效率。

该算法的目标是找到字符ch在字符串中第一次出现的位置并反转到这个位置的前缀。使用一个从左向右移动的右指针r可以有效地找到第一个出现的ch。如果从两端同时搜索，虽然可能在某些情况下更快找到ch，但需要额外的逻辑来确保找到的是第一次出现的位置，并且复杂度并没有明显优势，因此使用单一指针搜索是简单且有效的策略。

根据代码逻辑，如果字符ch不存在于字符串中，右指针r将会遍历整个字符串并停留在最后一个字符之后的位置。由于代码中包含了检查`if r < n`的条件，这个条件在ch不存在时不会满足，因此没有进行任何反转操作。最终函数会直接返回原始未修改的字符串。

在`while l < r`循环中，指针l和r分别从字符串的开始和ch字符的位置开始向对方移动。在每次循环中，l和r指向的字符被交换，然后l增加1，r减少1。这样的操作确保了从字符串的开始到ch的位置的每对字符都被交换一次。循环继续直到l不再小于r，这时所有需要被反转的字符都已经交换了位置。这个过程确保了字符前缀被正确地反转。