LeetCode-791. 自定义字符串排序【哈希表,字符串,排序】
LeetCode-791. 自定义字符串排序【哈希表,字符串,排序】
题目描述:
给定两个字符串 order 和 s 。order 的所有单词都是 唯一 的,并且以前按照一些自定义的顺序排序。
对 s 的字符进行置换,使其与排序的 order 相匹配。更具体地说,如果在 order 中的字符 x 出现字符 y 之前,那么在排列后的字符串中, x 也应该出现在 y 之前。
返回 满足这个性质的 s 的任意排列 。
示例 1:
输入: order = “cba”, s = “abcd”
输出: “cbad”
解释:
“a”、“b”、“c”是按顺序出现的,所以“a”、“b”、“c”的顺序应该是“c”、“b”、“a”。
因为“d”不是按顺序出现的,所以它可以在返回的字符串中的任何位置。“dcba”、“cdba”、“cbda”也是有效的输出。
示例 2:
输入: order = “cbafg”, s = “abcd”
输出: “cbad”
提示:
1 <= order.length <= 26
1 <= s.length <= 200
order 和 s 由小写英文字母组成
order 中的所有字符都 不同
https://leetcode.cn/problems/custom-sort-string/
解题思路一:哈希表,我们首先遍历给定的字符串 order,将第一个出现的字符的权值赋值为 0,第二个出现的字符的权值赋值为 1,以此类推。在遍历完成之后,所有未出现字符的权值默认赋值为 0。然后对s直接进行排序
unordered_map<char,int> mp;
bool cmp(char a,char b){//函数必须放在外面。
return mp[a]<mp[b];
}
class Solution {
public:
string customSortString(string order, string s) {
for(int i=0;i<order.size();++i) mp[order[i]]=i;
sort(s.begin(),s.end(),cmp);
return s;
}
};
时间复杂度:O(nlogn+m)n是s的长度
空间复杂度:O(m)m是order的长度
解题思路二:简化,三行代码!
class Solution {
public:
string customSortString(string order, string s) {
unordered_map<char,int> mp;
for(int i=0;i<order.size();++i) mp[order[i]]=i;
sort(s.begin(),s.end(),[&](char a,char b){return mp[a]<mp[b];});
return s;
}
};
时间复杂度:O(nlogn+m)n是s的长度
空间复杂度:O(m)m是order的长度
解题思路三:计数,对s出现的字符进行计数,节省时间。
1.我们首先遍历字符串 s,使用数组或哈希表统计每个字符出现的次数。
2.随后遍历字符串 order中的每个字符 c,如果其在 s 中出现了 k 次,就在答案的末尾添加 k 个 c,并将数组或哈希表中对应的次数置为 0。
3.最后我们遍历一次哈希表,对于所有次数 k 非 0 的键值对 (c,k),在答案的末尾添加 k 个 c 即可。
class Solution {
public:
string customSortString(string order, string s) {
vector<int> freq(26);
for (char ch: s) ++freq[ch - 'a'];
string ans;
for (char ch: order) {
if (freq[ch - 'a'] > 0) {
ans += string(freq[ch - 'a'], ch);
freq[ch - 'a'] = 0;
}
}
for (int i = 0; i < 26; ++i) {
if (freq[i] > 0) {
ans += string(freq[i], i + 'a');
}
}
return ans;
}
};
时间复杂度:O(n+m)n是s的长度
空间复杂度:O(m)m是order的长度
相关文章
- Java实现 LeetCode 757 设置交集大小至少为2(排序+滑动窗口)
- Java实现 LeetCode 1162 地图分析(可以暴力或者动态规划的BFS)
- Java实现 LeetCode 561 数组拆分 I(通过排序算法改写PS:难搞)
- Java实现 LeetCode 560 和为K的子数组(某著名排序大法改编)
- Java实现 LeetCode 516 最长回文子序列
- Java实现 LeetCode 451 根据字符出现频率排序
- Java实现 LeetCode 412 Fizz Buzz
- Java实现 LeetCode 376 摆动序列
- Java实现 LeetCode 292 Nim游戏
- Java实现 LeetCode 213 打家劫舍 II(二)
- Java实现 LeetCode 153 寻找旋转排序数组中的最小值
- Java实现 LeetCode 83 删除排序链表中的重复元素
- Java实现 LeetCode 80 删除排序数组中的重复项 II(二)
- Java实现 LeetCode 56 合并区间
- Java实现 LeetCode 41 缺失的第一个正数
- Java实现 LeetCode 33 搜索旋转排序数组
- Java实现 LeetCode 26 删除排序数组中的重复项
- Java实现 LeetCode 23 合并K个排序链表
- 【二分】LeetCode 33. 搜索旋转排序数组【中等】
- LeetCode(81): 搜索旋转排序数组 II
- 每日一道 LeetCode (18):删除排序链表中的重复元素
- LeetCode(67):二进制求和
- LeetCode-1604. 警告一小时内使用相同员工卡大于等于三次的人【哈希表,排序,数组】
- LeetCode-1592. 重新排列单词间的空格【字符串】
- leetcode 207. 课程表---拓扑排序篇一
- 【LeetCode 34】在排序数组中查找元素的第一个和最后一个位置
- leetCode 82.Remove Duplicates from Sorted List II (删除排序链表的反复II) 解题思路和方法
- leetcode 566. Reshape the Matrix
- 【LeetCode】153.寻找旋转排序数组中的最小值