Q1528 重新排列字符串-简单-编码排序

1528. 重新排列字符串

Question

给你一个字符串 s 和一个 长度相同 的整数数组 indices 。请你重新排列字符串 s ，其中第 i 个字符需要移动到 indices[i] 指示的位置。返回重新排列后的字符串

Example 1:

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

Example 2:

输入：s = "aiohn", indices = [3,1,4,2,0] 输出："nihao"

提示：

s.length == indices.length == n

1 <= n <= 100

s 仅包含小写英文字母。

0 <= indices[i] < n

indices 的所有的值都是唯一的（也就是说，indices 是整数 0 到 n - 1 形成的一组排列）。

Approach 1: 编码排序

本题目的容易出现歧义，需要仔细对案例进行分析才能正确理解题目意思。

本题目是先通过一种编码，把输入字符串中的每个字母对应上给定的序号。最后按照序号从小到大对字符串重排序。

理解题目后，就比较简单了，这里尝试一下使用enumerate()，返回s中每个字符的下标和对应字符

class Solution:
    def restoreString(self, s: str, indices ) -> str:
        result = [""] * len(s)
        for i, ch in enumerate(s):
            result[indices[i]] = ch
        return "".join(result)

    def restoreString1(self, s: str, indices ) -> str:
        res=['']*len(s)
        for i in range(len(indices)):
            res[indices[i]]=s[i]
        return "".join(res)

def main():
    s = "codeleet"
    indices = [4,5,6,7,0,2,1,3]
    solution=Solution().restoreString(s,indices)
    solution=Solution().restoreString1(s,indices)
    print(solution)


if __name__ == "__main__":
    main()

复杂度分析

时间复杂度：O(n)，n是字符串长度，需要遍历一遍字符串
空间复杂度：O(n)，n是字符串长度，只用申请一个长度为n的res数组。

其实也可以尝试不用申请res数组，直接修改原字符串，把空间复杂度降到O(1)。不过Python中要先用 s = list(s) 函数进行转化才能修改字符串。