Easy

题目描述

给你一个字符串 s 和一个长度相同的整数数组 indices。字符串 s 将会根据 indices 重新排列，其中第 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 的所有值都是唯一的

解题思路

解题思路

这道题要求我们根据给定的索引数组重新排列字符串。

核心思路： 题目的关键是理解重新排列的规则：原字符串第 i 位置的字符要移动到新字符串的 indices[i] 位置。

解法分析：

  1. 直接构造法（推荐）：创建一个新的字符数组，遍历原字符串，将每个字符按照索引数组的指示放到对应位置。

  2. 排序法：创建字符-索引对，按照目标索引排序后重新组合。

实现步骤：

  1. 创建长度为 n 的结果字符数组
  2. 遍历原字符串，将 s[i] 放到结果数组的 indices[i] 位置
  3. 将字符数组转换为字符串返回

这个方法时间复杂度最优，代码简洁易懂。

代码实现

class Solution {
public:
    string restoreString(string s, vector<int>& indices) {
        int n = s.length();
        string result(n, ' ');
        
        for (int i = 0; i < n; i++) {
            result[indices[i]] = s[i];
        }
        
        return result;
    }
};

class Solution:
    def restoreString(self, s: str, indices: List[int]) -> str:
        n = len(s)
        result = [''] * n
        
        for i in range(n):
            result[indices[i]] = s[i]
        
        return ''.join(result)

public class Solution {
    public string RestoreString(string s, int[] indices) {
        int n = s.Length;
        char[] result = new char[n];
        
        for (int i = 0; i < n; i++) {
            result[indices[i]] = s[i];
        }
        
        return new string(result);
    }
}

var restoreString = function(s, indices) {
    const n = s.length;
    const result = new Array(n);
    
    for (let i = 0; i < n; i++) {
        result[indices[i]] = s[i];
    }
    
    return result.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，n 为字符串长度
空间复杂度O(n)需要创建长度为 n 的结果数组