Leetcode 791 Custom Sort String

题意：给定两个字符串，第一个字符串order，给定字符出现的先后顺序。 第二个字符串需要按照第一个字符串的顺序重新排列。没有在order字符串中出现的数组随意排列

https://leetcode.com/problems/custom-sort-string/

解答：先根据第二个字符串计算得到频率map，然后遍历order（确保有序), 根据频率map构建新的字符串，并且频率相应更新。当遍历到order字符串末尾后，加上此时频率map中不为0的那些字符。

class Solution {
public:
    string customSortString(string order, string s) {
        unordered_map<char, int> mp;
        string res;
        for(char ch : s) {
            mp[ch]++;
        }
        for(char ch : order) {
            while (mp.count(ch) && mp[ch] != 0) {
                res += ch;
                mp[ch]--;
            }
        }
        
        for(auto& [k,v] : mp) {
            while(mp[k] != 0) {
                res += k;
                mp[k]--;
            }
        }
        return res;
    }
};

时间复杂度$O(n)$ $n$是字符串的长度
空间复杂度$O(n)$,频率数组有开销

原文地址：https://blog.csdn.net/xxxmmc/article/details/143742340

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！