重构字符串

╰半橙微兮° 2022-12-25 02:59 87阅读 0赞

> leetcode 767题 \[medium\]  
> 中：[重构字符串][Link 1]  
> 英：[Reorganize String][]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]

### 题解 ###

1.  判断是否具有重构字符串  
    （1）统计字符串中的最大字符重复数 most  
    （2）当且仅当 **剩余字符**(S.length - most) 无法填满 **重复字符形成的间隔**(most - 1) 时，重构不可行
2.  构建重构字符串  
    （1）统计字符串中最大字符重复数时会构建一个查询字典，键为字符，值为字符串中该字符出现的次数  
    （2）使用具有最大重复数的字符形成的重复字符串为**基串**  
    （3）依次将每一种剩余字符插入到**基串字符单元后**  
    （4）到达**基串末尾**，若还有剩余字符，基串中的旧字符与新插入字符组成**新的字符单元**，继续执行（3）的操作。  
    ![在这里插入图片描述][20201130135123799.gif]
3.  时间复杂度：O(n)
4.  空间复杂度：O(n + m) n用于记录结果，m为字符集的大小
5.  实现
    
        /** * @param {string} S * @return {string} */
        var reorganizeString = function(S) { 
            // 预处理（无）
        
            let map = new Map();        // 键为字符，值为字符出现的次数
            let most = [1, S[0]];       // most[0] 字符出现的最多次数; most[1] 出现最多次数的字符
            map.set(S[0], 1);
            // 构建map
            for(let i=S.length-1; i>0; i--){ 
                let currChar = S[i];
                if(map.has(currChar)){ 
                    let times = map.get(currChar) + 1;
                    map.set(currChar, times);
                    if (times > most[0]) { 
                        most[0] = times;
                        most[1] = currChar;
                    }
                }
                else map.set(currChar, 1);
            }
        
            // 重构不可行（剩余字符 无法填满 重复字符形成的间隔）
            if(S.length - most[0] < most[0] - 1) return "";
        
            // 重构可行
            let resultArr = Array.from({ length: most[0]}, () => most[1]);   // 最大重复数的字符列表
            map.delete(most[1]);
            // 遍历每一种剩余字符，每次将一个字符拼接到resultArr的每一项中
            let currIdx = 0;
            map.forEach((times, char)=>{ 
                for(let i=0; i<times; i++){ 
                    resultArr[currIdx] += char;
                    currIdx = (currIdx+1) % most[0];
                }
            })
            
            // 列表转字符串
            return resultArr.join('');
        };

[Link 1]: https://leetcode-cn.com/problems/reorganize-string/
[Reorganize String]: https://leetcode.com/problems/reorganize-string/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]: /images/20221120/3f0a4b07e13849fab2966918d116b68a.png
[20201130135123799.gif]: /images/20221120/35d78658209a4684b541fd3430e90a11.png