↓快轉到主要內容
  1. Leetcode/

[LeetCode] 767. Reorganize String

·
LeetCode priority queue
目錄

題目連結：767. Reorganize String

解題思路
#

單純使用 frequency 來維護 priority queue 對於實作還是有許多困難，因此考慮使用 pair<frequency, char> 來維護 pq。每次 pop 出 freq 最大的兩個字元，append 進字串後將 freq - 1 push 回 pq 裡。迴圈終止的條件是當 pq size ≤ 1 時。

程式碼
#

class Solution {
public:
    string reorganizeString(string s) {
        string res;
        vector<int> freq(26, 0);
        priority_queue<pair<int, char>> pq;

        for (int i = 0; i < s.size(); i++) {
            freq[s[i]-'a']++;
        }

        for (int i = 0; i < 26; i++) {
            if (!freq[i]) continue;
            pq.push({freq[i], i + 'a'});
        }

        while (pq.size() > 1) {
            auto a = pq.top(); pq.pop();
            auto b = pq.top(); pq.pop();

            res.push_back(a.second);
            res.push_back(b.second);

            if (a.first - 1) pq.push({a.first - 1, a.second});
            if (b.first - 1) pq.push({b.first - 1, b.second});
        }

        if (!pq.empty()) {
            auto a = pq.top(); pq.pop();
            if (a.first == 1)
                res.push_back(a.second);
            else
                return "";
        }

        return res;
    }
};