题目描述：

LeetCode 767. Reorganize String

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

题目大意：

给定字符串S，将其中的字母重新排列，使得相邻的字符均不相同。

若不存在这样的排列，返回空串。

解题思路：

贪心算法（Greedy Algorithm）

将字母按照出现次数从大到小排序。

每次优先选择剩余次数最多，且与新字符串末尾字符串不重复的字符，排在末尾。

若某次选择无法找出这样的字符，则返回空串。

Python代码：

class Solution(object):
    def reorganizeString(self, S):
        """
        :type S: str
        :rtype: str
        """
        cnt = collections.Counter(S)
        ans = '#'
        while cnt:
            stop = True
            for v, c in cnt.most_common():
                if v != ans[-1]:
                    stop = False
                    ans += v
                    cnt[v] -= 1
                    if not cnt[v]: del cnt[v]
                    break
            if stop: break
        return ans[1:] if len(ans) == len(S) + 1 else ''

 

本文链接：http://bookshadow.com/weblog/2018/01/21/leetcode-reorganize-string/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码