leetcode
leetcode 1751 ~ 1800
反转单词前缀

反转单词前缀

难度:

标签:

题目描述

代码结果

运行时间: 22 ms, 内存: 16.1 MB


// Java Stream Solution
// 思路:
// 1. 使用流来查找字符 ch 在字符串 word 中第一次出现的下标 i。
// 2. 如果找到字符 ch,使用流处理并反转相应部分的字符。
// 3. 将反转后的部分与剩余部分拼接,得到结果字符串。

import java.util.OptionalInt;
import java.util.stream.IntStream;

public class Solution {
    public String reversePrefix(String word, char ch) {
        OptionalInt optionalIndex = IntStream.range(0, word.length())
                                             .filter(i -> word.charAt(i) == ch)
                                             .findFirst();
        if (!optionalIndex.isPresent()) {
            return word;
        }
        int index = optionalIndex.getAsInt();
        String reversedPart = new StringBuilder(word.substring(0, index + 1)).reverse().toString();
        return reversedPart + word.substring(index + 1);
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
解题思路中提到将输入字符串转换为字符列表以便进行原地修改,这种方式与直接在字符串上操作有何优势?
在Python中,字符串是不可变的数据类型,这意味着无法直接修改字符串中的单个字符。因此,要实现原地修改的效果,必须先将字符串转换为可变的数据结构,如字符列表。这样可以在列表中直接进行字符的交换,操作完成后再将列表转换回字符串。这种方法相比于每次修改都生成新的字符串,可以节省内存消耗,并可能提高执行效率。
🦆
在查找字符ch的过程中,为什么选择只使用一个右指针r进行移动而不考虑从字符串两端同时搜索?
该算法的目标是找到字符ch在字符串中第一次出现的位置并反转到这个位置的前缀。使用一个从左向右移动的右指针r可以有效地找到第一个出现的ch。如果从两端同时搜索,虽然可能在某些情况下更快找到ch,但需要额外的逻辑来确保找到的是第一次出现的位置,并且复杂度并没有明显优势,因此使用单一指针搜索是简单且有效的策略。
🦆
如果字符ch不存在于字符串中,返回的结果是原字符串还是进行了某种处理的字符串?代码中似乎没有明确指出。
根据代码逻辑,如果字符ch不存在于字符串中,右指针r将会遍历整个字符串并停留在最后一个字符之后的位置。由于代码中包含了检查`if r < n`的条件,这个条件在ch不存在时不会满足,因此没有进行任何反转操作。最终函数会直接返回原始未修改的字符串。
🦆
请问在反转字符的过程中,使用`while l < r`循环的具体逻辑是如何确保所有需要反转的字符都被正确交换的?
在`while l < r`循环中,指针l和r分别从字符串的开始和ch字符的位置开始向对方移动。在每次循环中,l和r指向的字符被交换,然后l增加1,r减少1。这样的操作确保了从字符串的开始到ch的位置的每对字符都被交换一次。循环继续直到l不再小于r,这时所有需要被反转的字符都已经交换了位置。这个过程确保了字符前缀被正确地反转。

相关问题