首页 > 其他 > 详细

Leetcode 767. Reorganize String

时间:2021-04-05 12:46:08      阅读:16      评论:0      收藏:0      [点我收藏+]

Description: Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result.  If not possible, return the empty string.

Link: 767. Reorganize String

Examples:

Example 1:
Input: S = "aab"
Output: "aba"

Example 2:
Input: S = "aaab"
Output: ""

Note: S will consist of lowercase letters and have length in range [1, 500].

思路: 将S按照频率由大到小重新排列,将频率最高的字母取出待处理,检查剩余字母是否足够间隔开最高频率的子串,假设最高频字母为k,出现v次,那么剩余字母个数大于等于v-1个就够了,否则返回 ‘‘, 将未使用过的子串S = S[v+v-1:]重复以上步骤,直到S为空。

class Solution(object):
    def reorganizeString(self, S):
        """
        :type S: str
        :rtype: str
        """
        res = ‘‘
        while len(S) > 0:
            counter = collections.Counter(S)
            s = ‘‘
            for k, v in counter.most_common():
                s += k*v
            k, v = counter.most_common(1)[0]
            if len(s) - v < v-1:
                return ‘‘
            i = 0
            sr = list(s[v:])
            for i in range(v-1):
                res += k + sr[0]
                sr.pop(0)
            res += k
            S = sr
        return res

日期: 2021-04-05 刷题真快乐

Leetcode 767. Reorganize String

原文:https://www.cnblogs.com/wangyuxia/p/14617788.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!