Solution by bromanz


  • 0

    alttext

    Approach #1 Tracking position [Accepted]

    Intuition

    The starting position in a 2D-coordinate system or grid is $$(0,0)$$. We have to track the movement and check whether the position is $$(0,0)$$ again in the end.

    Algorithm

    Save the current position for each axis. Go through each character in the input string and apply each global movement step to the current position. In the end, test if the final position is $$(0,0)$$.

    Java

    public boolean judgeCircle(String moves) {
      int x = 0;
      int y = 0;
    
      for(int i=0;i<moves.length();i++) {
          switch (moves.charAt(i)) {
              case 'U':
                  y++;
                  break;
              case 'D':
                  y--;
                  break;
              case 'L':
                  x--;
                  break;
              case 'R':
                  x++;
                  break;
          }
      }
    
      if(x==0 && y==0)
        return true;
      else
        return false;
    }
    

    C#

    public bool JudgeCircle(string moves)
    {
       int x=0;
       int y=0;
    
       foreach (char c in moves)
       {
         switch (c)
         {
             case 'U':
                 y++;
                 break;
             case 'D':
                 y--;
                 break;
             case 'L':
                 x--;
                 break;
             case 'R':
                 x++;
                 break;
         }
       }
    
       if(x==0 && y==0)
          return true;
       else
          return false;
    }
    

    C++

    bool judgeCircle(string moves) {
    	int x = 0;
    	int y = 0;
    	for each (char c in moves) {
    		switch (c) {
        		case 'U':
        			y++;
        			break;
        		case 'D':
        			y--;
        			break;
        		case 'L':
        			x--;
        			break;
        		case 'R':
        			x++;
        			break;
    		}
    	}
    
      if (x == 0 && y == 0)
        return true;
      else
        return false;
    }
    

    JavaScript

    var judgeCircle = function (moves) {
      var x = 0;
      var y = 0;
    
      for(var i=0;i<moves.length;i++) {
          switch (moves[i]) {
              case 'U':
                  y++;
                  break;
              case 'D':
                  y--;
                  break;
              case 'L':
                  x--;
                  break;
              case 'R':
                  x++;
                  break;
          }
      }
    
      if (x == 0 && y == 0)
        return true;
      else
        return false;
    };
    

    Python

    def judgeCircle(self, moves):
        x = 0
        y = 0
    
        for c in moves:
            if c=='U': y+=1
            elif c=='D' : y-=1
            elif c=='R' : x+=1
            else: x-=1
    
        if x==0 and y==0: return True
    
        return False
    

    Complexity Analysis

    • Time complexity : $$O(n)$$. We have to iterate over each character in the input string of length $$n$$.
    • Space complexity : $$O(1)$$. We need constant space (two integers).

    Approach #2 Compare opposing movements [Accepted]

    Intuition

    If the robot moves $$n$$ times in a certain direction, he has to take $$n$$ opposing moves to return to his starting position.

    Algorithm

    Go through the string and count the number of up, down, left, and right moves. Compare if the number of up moves is equal to the number of down moves and if the number of left moves is equal to the number of right moves.

    (The following implementations show variations of how the counting of character occurrences in a string can be achieved.)

    Java

    public boolean judgeCircle(String moves) {
       int u = 0;
       int d = 0;
       int l = 0;
       int r = 0;
    
       for(int i=0;i<moves.length();i++) {
           switch (moves.charAt(i)) {
               case 'U':
                   u++;
                   break;
               case 'D':
                   d++;
                   break;
               case 'L':
                   l++;
                   break;
               case 'R':
                   r++;
                   break;
           }
       }
    
       return (u==d && l==r);
    }
    

    C#

    public bool JudgeCircle(string moves)
    {
       return (moves.Split('U').Length == moves.Split('D').Length && moves.Split('L').Length == moves.Split('R').Length);
    }
    

    C++

    bool judgeCircle(string moves) {
        int u = count(moves.begin(), moves.end(), 'U');
        int d = count(moves.begin(), moves.end(), 'D');
        int l = count(moves.begin(), moves.end(), 'L');
        int r = count(moves.begin(), moves.end(), 'R');
    
        return (u==d && l==r);
    }
    

    JavaScript

    var judgeCircle = function (moves) {
      return moves.split("U").length == moves.split("D").length && moves.split("L").length == moves.split("R").length;
    };
    

    Python

    def judgeCircle(self, moves):
           return moves.count('U') == moves.count('D') and moves.count('L') == moves.count('R')
    

    Complexity Analysis

    • Time complexity : $$O(n)$$. We have to iterate over each character in the input string and count the occurrences of U, D, L, R respectively.
    • Space complexity : $$O(1)$$. We usually need constant space (four integers). If you count in the temporary arrays which the "Split" methods return, the space complexity would be $$O(U+D+L+R)$$ whereas $$U, D, L, R$$ are the number of the respective character occurrences.


Log in to reply
 

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