【LeetCode】自定义字符串排序 Java 题解
题目描述
给定两个字符串 order 和 s 。order 的所有字母都是 唯一 的，并且以前按照一些自定义的顺序排序。
对 s 的字符进行置换，使其与排序的 order 相匹配。更具体地说，如果在 order 中的字符 x 出现字符 y 之前，那么在排列后的字符串中， x 也应该出现在 y 之前。
返回 满足这个性质的 s 的任意一种排列 。
复制代码
思路分析
今天的算法题目是字符串处理题目，题目要求按照自定义字符串排序。其中,order 就是一个给定好的顺序。那我们如何应用这个顺序呢？有一种算法就是将这个 order 的每一个字符给予相应的权重。我们可以定义一个字符权重数组 sortWeight,每个字符默认的权重都是 0，然后 order 中的字符逐个计算权重。
计算完成权重之后，我们可以将 s 转换成字符数组。直接使用 Arrays.sort()排序。sort() 方法不返回任何值，它只是更改动态数组列表中元素的顺序。由于是自定义排序，我们需要重 Override comparator 方式，比较的时候使用我们计算的好的 sortWeight。
具体实现代码如下，供参考。
通过代码
复制代码
总结
普通算法的时间复杂度是 O(n * log n)，空间复杂度是 O(n)。
坚持算法每日一题，加油！
版权声明: 本文为 InfoQ 作者【Albert】的原创文章。
原文链接:【http://xie.infoq.cn/article/313ee2914892ba6b2c9e805b0】。文章转载请联系作者。
数据结构和算法爱好者 2019-09-29 加入
LeetCode,略懂后端的RD
评论