動機

先看621

Problem

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return if not possible.

 

Example 1:

Input: s = aabOutput: aba

Example 2:

Input: s = aaabOutput:

 

Constraints:

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.

Sol

class Solution:
    def reorganizeString(self, s: str) -> str:
        cs = Counter(s)
        ret = [None]*len(s)
        start = 0
        while cs:
            mostc, most = cs.most_common(1)[0]
            del cs[mostc]
            if start < len(s):
                for i in range(start,start+most*2,2):
                    if i < len(s):
                        ret[i] = mostc
                        if cs:
                            submostc, submost = cs.most_common(1)[0]
                            if submost == 1:
                                del cs[submostc]
                            else:
                                cs[submostc] -= 1
                            ret[i+1] = submostc
                            start = i+2
                            #print(start, cs, ret)
                    else:
                        return ""
            else:
                return ""
        return ''.join(ret)

用exception拿掉一些if

class Solution:
    def reorganizeString(self, s: str) -> str:
        cs = Counter(s)
        ret = [None]*len(s)
        start = 0
        try:
            while cs:
                mostc, most = cs.most_common(1)[0]
                del cs[mostc]
                for i in range(start,start+most*2,2):
                    ret[i] = mostc
                    if cs:
                        submostc, submost = cs.most_common(1)[0]
                        if submost == 1:
                            del cs[submostc]
                        else:
                            cs[submostc] -= 1
                        ret[i+1] = submostc
                        start = i+2
                        #print(start, cs, ret)
            return ''.join(ret)
        except:
            return ""