0767._Reorganize_String.md

767. Reorganize String

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/reorganize-string/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.

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].

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******

先按照出现频率排序，然后频率越大的字母越往后面放，加入某个字母出现频率大于len(S)+1，一定不能满足条件，直接返回''

最后采用插空法，先把前半段固定，后半段插空即可

beats 100%

class Solution(object):
    def reorganizeString(self, S):
        """
        :type S: str
        :rtype: str
        """
        lookup = {}
        reorg_S, res = [], [0] * len(S)
        for c in S:
            lookup[c] = lookup.get(c, 0) + 1
            if lookup[c] > (len(S) + 1) / 2:
                return ''
        chars = sorted([key for key in lookup.keys()], key = lambda x: lookup[x])
        for key in chars:
            reorg_S.extend([key] * lookup[key])
        res[::2], res[1::2] = reorg_S[len(S)/2:], reorg_S[:len(S)/2]
        return ''.join(res)