68ms Python Solution


  • 0
    L

    The senate string can be winded up as a circle.

    For each senator, the best choice is to ban the first opponent who is able to vote in the future.

    The solution uses banned_d and banned_r to record how many d-senator / r-senator will be banned.

    When it comes to a senator to vote, say it's a d-sanator:

    • if banned_d == 0 (no d-senator will be banned), this d-senator bans an opponent (banned_r += 1) and stays in the senate to the next round.
    • otherwise (banned_d > 0), this d-senator is sacrificed and banned_d head count becomes smaller.

    Once the senate has no r-senators, "Dire" wins. And vice versa.

      def predictPartyVictory(self, s):
            banned_d = banned_r = 0
            while True:
                s2 = []
                has_d = has_r = False
                for c in s:
                    if c == 'R':
                        if banned_r == 0:
                            s2.append('R')
                            has_r = True
                            banned_d += 1
                        else:
                            banned_r -= 1
                    else:
                        if banned_d == 0:
                            s2.append('D')
                            has_d = True
                            banned_r += 1
                        else:
                            banned_d -= 1
                if not has_d: return 'Radiant'
                if not has_r: return 'Dire'
                s = s2
    

  • 0
    P

    Same idea - update the string, but with a different way to terminate:
    when one party is twice outnumbering the other at the end of the round (same as at the start), then this party will win.

    from collections import Counter
    class Solution(object):
        def predictPartyVictory(self, senate):
            """
            :type senate: str
            :rtype: str
            """
            res = {'R': 'Radiant', 'D':'Dire'}
            ban = Counter()
            while senate:
            	new = ""
    	        for i in senate:
    	        	if ban[ i ] > 0:
    	        		ban[ i ] -= 1
    	        	else:
    	        		new += i
    	        		ban[ chr(150-ord(i)) ] += 1
    	        for c in 'RD':
    	        	if new.count(c) > new.count(chr(150-ord(c))) * 2:
    	        		return res[c]
    	        senate = new
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.