重新排列字符串
难度:
标签:
题目描述
给你一个字符串 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`而不是在原数组`s`上就地修改?
▷🦆
如果`indices`数组不是有效的索引序列(例如包含重复或超出范围的索引),该算法会如何处理?
▷