Java recursive solution, beat 95%


  • 0
    L

    First of all, the best strategy for everyone is to ban the opponent senator just next to himself.

    Notice that at any given point during the iteration, we can know that which side is leading and how many they lead (meaning that following opponents will be banned). So we store this info in a variable banD. For example, banD == 2 means that 2 following D senators will be banned and banD == -2 means that 2 following R senators will be banned.

    Then the recursive method simulates a real voting process. If a senator is not banned, we leave it to the next round. And keep the leading information among rounds.

    class Solution {
      int banD = 0;
      public String predictPartyVictory(String senate) {
        StringBuilder sb = new StringBuilder();
        int countR = 0;
        for (int i = 0; i < senate.length(); i++) {
          if (senate.charAt(i) == 'R') {
            if (banD >= 0) {
              sb.append('R');
              countR++;
            }
            banD++;
          } else {
            if (banD <= 0)
              sb.append('D');
            banD--;
          }
        }
        if (countR == 0)
          return "Dire";
        if (countR == sb.length())
          return "Radiant";
        return predictPartyVictory(sb.toString());
      }
    }
    

Log in to reply
 

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