[LeetCode] Custom Sort String 自定义排序的字符串
S
and T
are strings composed of lowercase letters. In S
, no letter occurs more than once.
S
was sorted in some custom order previously. We want to permute the characters of T
so that they match the order that S
was sorted. More specifically, if x
occurs before y
in S
, then x
should occur before y
in the returned string.
Return any permutation of T
(as a string) that satisfies this property.
Example : Input: S = "cba" T = "abcd" Output: "cbad" Explanation: "a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a". Since "d" does not appear in S, it can be at any position in T. "dcba", "cdba", "cbda" are also valid outputs.
Note:
S
has length at most26
, and no character is repeated inS
.T
has length at most200
.S
andT
consist of lowercase letters only.
这道题给了我们两个字符串S和T,让我们将T按照S的顺序进行排序,就是说在S中如果字母x在字母y之前,那么排序后的T中字母x也要在y之前,其他S中未出现的字母位置无所谓。那么我们其实关心的是S中的字母,只要按S中的字母顺序遍历,对于遍历到的每个字母,如果T中有的话,就先排出来,这样等S中的字母遍历完了,再将T中剩下的字母加到后面即可。所以我们先用HashMap统计T中每个字母出现的次数,然后遍历S中的字母,只要T中有,就将该字母重复其出现次数个,加入结果res中,然后将该字母出现次数重置为0。之后再遍历一遍HashMap,将T中其他字母加入结果res中即可,参见代码如下:
解法一:
class Solution { public: string customSortString(string S, string T) { string res = ""; unordered_map<char, int> m; for (char c : T) ++m[c]; for (char c : S) { res += string(m[c], c); m[c] = 0; } for (auto a : m) { res += string(a.second, a.first); } return res; } };
下面这种解法的思路和上面的一样,只不过这里没有使用HashMap,而是使用了一个长度为26的数组,因为题目中说了S和T中都是小写的字母,其他部分没有啥太大的区别,参见代码如下:
解法二:
class Solution { public: string customSortString(string S, string T) { string res = ""; vector<int> cnt(26, 0); for (char c : T) ++cnt[c - 'a']; for (char c : S) { while (cnt[c - 'a']-- > 0) res.push_back(c); } for (char c : T) { while (cnt[c - 'a']-- > 0) res.push_back(c); } return res; } };
下面这种方法可以说是简洁的让人发指啊,就两行搞定碉堡了。我们自定义了sort的排序的排序方式,对于字符串T中的任意两个字母a和b,按照其在S中的顺序排序,在S中排前面的在T中也排前面,完全符合题意,所以就能很好的work,参见代码如下:
解法三:
class Solution { public: string customSortString(string S, string T) { sort(T.begin(), T.end(), [&](char a, char b) {return S.find(a) < S.find(b);}); return T; } };
下面这种解法没有用到STL中内置的find函数,而是用了HashMap来建立S中每个字母和其出现位置之间的映射,这样在自定义排序方法的时候,就可以直接从HashMap中取位置了,参见代码如下:
解法四:
class Solution { public: string customSortString(string S, string T) { unordered_map<char, int> m; for (int i = 0; i < S.size(); ++i) { m[S[i]] = i + 1; } sort(T.begin(), T.end(), [&](char a, char b) {return m[a] < m[b];}); return T; } };
类似题目:
https://leetcode.com/problems/custom-sort-string/solution/
https://leetcode.com/problems/custom-sort-string/discuss/116556/Two-Lines-C++
相关文章
- leetcode 149. 直线上最多的点数 解题报告
- 【Leetcode】2105. 给植物浇水 II(中等)
- JS Leetcode 179. 最大数 题解分析,sort a-b与b-a的区别,sort排序原理解析
- JS Leetcode 33. 搜索旋转排序数组题解,图解旋转数组中的二分法
- 简单易用的leetcode开发测试工具(npm)
- [LeetCode] Unique Binary Search Trees II
- [LeetCode]804. 唯一摩尔斯密码词
- [LeetCode]258. 各位相加
- LeetCode 912. 排序数组
- LeetCode | 一探环形链表的奥秘【快慢双指针妙解BAT等大厂经典算法题】
- LeetCode之347前 K 个高频元素(相关话题:堆排序,桶排序)
- LeetCode 26. 删除排序数组中的重复项
- [LeetCode] 1129. Shortest Path with Alternating Colors 颜色交替的最短路径
- [LeetCode] 922. Sort Array By Parity II 按奇偶排序数组之二
- [LeetCode] Number of Subarrays with Bounded Maximum 有界限最大值的子数组数量
- [LeetCode] Random Pick with Weight 根据权重随机取点
- [LeetCode] 654. Maximum Binary Tree 最大二叉树
- [LeetCode] Sort Characters By Frequency 根据字符出现频率排序
- [LeetCode] 390. Elimination Game 淘汰游戏
- [LeetCode] 293. Flip Game 翻转游戏
- [LeetCode] Contains Duplicate III 包含重复值之三
- [LeetCode] 75. Sort Colors 颜色排序
- [LeetCode] 67. Add Binary 二进制数相加
- leetcode 513. Find Bottom Left Tree Value 找树左下角的值 (简单)
- leetcode 83. Remove Duplicates from Sorted List 删除排序链表中的重复元素(简单)
- leetcode 769. Max Chunks To Make Sorted 最多能完成排序的块(中等)
- leetcode 204. Count Primes 计数质数 (Easy)
- leetcode 81. Search in Rotated Sorted Array II 搜索旋转排序数组 II(中等)
- leetcode 34. Find First and Last Position of Element in Sorted Array 在排序数组中查找元素的第一个和最后一个位置(中等)