题目

标题和出处

标题：重新排列字符串

出处：1528. 重新排列字符串

难度

3 级

题目描述

要求

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

请你重新排列字符串 ，其中第 个字符需要移动到 指示的位置。

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

示例

示例 1：

输入：
输出：
解释：如图所示， 重新排列后变为 。

示例 2：

输入：
输出：
解释：重新排列后，每个字符都还留在原来的位置上。

示例 3：

输入：
输出：

示例 4：

输入：
输出：

示例 5：

输入：
输出：

数据范围

• 
• 
• 仅包含小写英文字母
• 
• 的所有的值都是唯一的（ 是整数 到 形成的一组排列）

解法

思路和算法

假设将字符串 根据数组 重新排列后的字符串是 ，则 的第 个字符在 中位于第 个位置，即 。

遍历字符串 和数组 的过程中，即可知道 的每个字符在 中的位置。可以创建一个 类型的数组 存储 的结果。对于长度为 的字符串 和数组 ，当 时，将 赋值给 即可。

遍历结束之后， 的全部位置都填入了字符，将 转成字符串，即为重新排列后的字符串。

代码

class Solution {
    public String restoreString(String s, int[] indices) {
        int n = indices.length;
        char[] array = new char[n];
        for (int i = 0; i < n; i++) {
            array[indices[i]] = s.charAt(i);
        }
        return new String(array);
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28n%29&id=Rnxa9)，其中 是字符串 和数组 的长度。需要遍历字符串 一次，遍历的过程中重新排列字符串，新字符串的每个位置的字符需要 #card=math&code=O%281%29&id=lGdaq) 的时间填入。
• 空间复杂度：#card=math&code=O%28n%29&id=PEuGm)，其中 是字符串 和数组 的长度。需要额外创建一个长度为 的 类型的数组用于存储重新排列后的字符串。由于 Java 中的 类型的对象不可变，因此空间复杂度至少为 #card=math&code=O%28n%29&id=PvJ7V)。