leetcode
leetcode 1401 ~ 1450
重新排列字符串

重新排列字符串

难度:

标签:

题目描述

给你一个字符串 s 和一个 长度相同 的整数数组 indices

请你重新排列字符串 s ,其中第 i 个字符需要移动到 indices[i] 指示的位置。

返回重新排列后的字符串。

 

示例 1:

输入:s = "codeleet", indices = [4,5,6,7,0,2,1,3]
输出:"leetcode"
解释:如图所示,"codeleet" 重新排列后变为 "leetcode" 。

示例 2:

输入:s = "abc", indices = [0,1,2]
输出:"abc"
解释:重新排列后,每个字符都还留在原来的位置上。

 

提示:

  • s.length == indices.length == n
  • 1 <= n <= 100
  • s 仅包含小写英文字母
  • 0 <= indices[i] < n
  • indices 的所有的值都是 唯一

代码结果

运行时间: 43 ms, 内存: 0.0 MB


/*
 * 题目思路:
 * 1. 使用 IntStream 来生成索引流。
 * 2. 使用 Collectors.toMap 方法将每个字符放置在新的索引位置。
 * 3. 使用 map.entrySet().stream() 获取所有的映射关系并排序。
 * 4. 最后将排序后的字符收集成字符串并返回。
 */
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public String restoreString(String s, int[] indices) {
        return IntStream.range(0, s.length())
                .boxed()
                .collect(Collectors.toMap(i -> indices[i], i -> s.charAt(i)))
                .entrySet()
                .stream()
                .sorted(Map.Entry.comparingByKey())
                .map(Map.Entry::getValue)
                .collect(Collectors.collectingAndThen(Collectors.toList(), list -> {
                    StringBuilder sb = new StringBuilder();
                    list.forEach(sb::append);
                    return sb.toString();
                }));
    }
}

解释

方法:

该题解的基本思路是使用一个辅助数组res,其长度与输入字符串s相同。首先初始化res为全空字符串数组。然后遍历字符串s的每个字符及其对应的索引,将字符放置到res数组的indices指定的位置。最后,使用join方法将res数组中的字符合并成一个字符串作为最终结果。这种方法直接根据indices数组的指示进行字符的重新定位,避免了不必要的字符交换操作。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在题解中提到的`res = [''] * len(s)`初始化方法是否存在风险,例如在并发环境下,是否会产生竞争条件问题?
在本题的上下文中,使用`res = [''] * len(s)`来初始化一个新的字符串列表是安全的,因为列表中每个元素都是独立的空字符串,不存在对象共享的问题。然而,在并发环境下,如果多个线程试图修改同一个`res`数组的不同部分,那么确实可能会出现竞争条件。但这种情况通常需要明确的多线程代码实现及同步措施(如使用锁)。在单线程的执行环境中,这种初始化方法是安全且有效的。
🦆
为什么该算法选择使用额外的数组`res`而不是在原数组`s`上就地修改?
在原字符串`s`上进行就地修改可能会更加复杂,因为字符串在许多编程语言中是不可变的,这意味着任何修改都需要创建一个新的字符串对象,可能导致效率降低。即使在允许修改字符串的语言中,就地修改也需要复杂的逻辑来管理已移动和尚未移动的字符,增加了错误出现的机会。使用额外的数组`res`可以直接按照索引放置字符,实现简单且效率高。
🦆
如果`indices`数组不是有效的索引序列(例如包含重复或超出范围的索引),该算法会如何处理?
该算法没有内置处理无效索引的机制。如果`indices`数组包含重复的索引,某些位置可能会被多次赋值,而其他位置则可能留空,导致结果字符串不完整或错误。如果`indices`中的索引超出了数组`res`的范围,将会引发索引越界错误。在实际应用中,应该在调用此函数前验证`indices`数组的有效性,确保所有索引都是唯一且在合法范围内。

相关问题