[Leetcode题解]重构字符串

767. 重构字符串

image.png

思路:使用哈希表,将字符串按照频率排序后 组装在一起。这个时候重点来了,怎么样让这些相同的字符不相邻的,技巧就是使用切片!
因为排序后相邻的字符是一样的,所以,我们把前半部分(等于或者大于后边一个),按照间隔的放到结果字符串中。然后把后半部分同理。

代码如下:

class Solution(object):
    def reorganizeString(self, S):
        """
        :type S: str
        :rtype: str
        """
        n = len(S)

        A = []
        for c,x in sorted((S.count(x),x) for x in set(S)):
            if c>(n+1)/2:return ""
            A.extend(c*x)

        ans = [None]*n

        ans[::2],ans[1::2] = A[n//2:],A[:n//2]

        return "".join(ans)

评论

暂无评论