【LeetCode-字符串】重构字符串

题目描述

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。
示例：

输入: S = "aab"
输出: "aba"

输入: S = "aaab"
输出: ""

说明：

• S 只包含小写字母并且长度在[1, 500]区间内。

题目链接： https://leetcode-cn.com/problems/reorganize-string/

思路

假设 S 中有多个 a，则我们想让字符串排成 aXaXaX 的形式。我们可以先统计每个字符出现的次数，然后利用间隔插值的方法来将字符插入一个长度为 S.size() 的数组中，最后将数组转为字符串返回。

我们将 S 中的每一个字符编码成一个数字 n，n/100 表示字符出现的次数，n%100+'a' 表示该字符。例如，假设 S='aabbb'，则 'b' 被编码为 301。这样做的好处是我们可以只通过编码获得该编码对应的字符以及该字符出现的次数。

字符的编码存储在数组 code 中，然后我们将 code 中的元素升序排序，排序前 code[i] 表示的字符是 i+'a'，排序后就不能这么对应了，但是我们可以通过 code[i] 的编码来推出 code[i] 对应的是哪个字符。升序排序的目的是先将出现次数较少的字符插入到答案中，然后再插入出现次数较多的字符。这样可以避免出错。

遍历 code，根据 code 中的值解码得到字符和该字符出现的次数，然后将其插入到数组中即可。

代码如下：

class Solution {
public:
    string reorganizeString(string S) {
        string s = S;
        if(s.empty()) return s;

        vector<int> code(26, 0);
        for(int i=0; i<s.size(); i++){
            code[s[i]-'a'] += 100;
        }
        for(int i=0; i<code.size(); i++) code[i] += i;
        sort(code.begin(), code.end());

        vector<char> ans(s.size(), ' ');
        int t = 1;
        for(int i=0; i<code.size(); i++){
            int cnt = code[i]/100;
            if(cnt>(s.size()+1)/2) return ""; // 无解
            char c = char('a'+code[i]%100);
            for(int j=0; j<cnt; j++){
                if(t>=s.size()) t=0;
                ans[t%s.size()] = c;
                t += 2;
            }
        }

        string ansStr(ans.begin(), ans.end());
        return ansStr;
    }
};

这个插入方式很特别，首先令 t = 1，如果 t>S.size()，就将 t 重置为 0；否则 t += 2.

参考

https://leetcode-cn.com/problems/reorganize-string/solution/zhong-gou-zi-fu-chuan-by-leetcode/