Solution by pratiksanglikar


  • 0
    P

    Approach #1 Brute Force [Accepted]

    Intuition
    There are four valid moves for the Robot, these moves are -
    Left 'L', Right 'R', Up 'U' and Down 'D'.

    These moves can be categorized as pairs of opposite moves.
    i.e. Left 'L' is an opposite move of Right 'R'
    and Up 'U' is an opposite move of the move Down 'D'.

    To determine if the Robot has reached it's original position, it is enough to check for each move, there is an opposite move.

    i.e. for each Left 'L' move, there should be a Right 'R' move and for each Up 'U' move, there should be a Down 'D' move.

    Algorithm
    Now we know that for each horizontal and vertical move, if there is an opposite move, the Robot has reached it's original place. We can maintain two variables - verticalMoves and horizontalMoves which maintain the count of the vertical and horizontal moves.
    for each left move, we increment the horizontalMoves variable and we decrement the variable if an opposite move i.e. right move occurs.
    Same thing can be done for the variable verticalMoves, we increment the verticalMoves variable if there is an up move and we decrement the variable if an opposite move i.e. down move occurs.

    at the end, if there are equal number of left and right moves, the value in the variable horizontalMoves will be 0 and if there are equal number of up and down moves, the value in the variable verticalMoves will be 0.

    Essentially, if values in the both variables horizontalMoves and verticalMoves is 0, the Robot has reached it's original position.

    let verticalMoves := 0, horizontalMoves := 0
    for each move in the input
        if move = leftmove
            horizontalMoves := horizontalMoves + 1
        else if move = rightmove
            horizontalMoves := horizontalMoves - 1
        else if move = upmove
            verticalMoves := verticalMoves + 1
        else if move = downmove
            verticalMoves := verticalMoves - 1
    end for
    if verticalMoves = 0 and horizontalMoves = 0
        return true
    else
        return false
    

    Java

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

    Complexity Analysis

    • Time complexity: $$O(n)$$.
      Since we need to traverse each character of the input string only once, the time complexity becomes $$O(n)$$.

    • Space complexity: $$O(1)$$.
      Since there are only two extra variables - horizontalMoves and verticalMoves, the space used is not dependent on the size of the input string.
      Since the space used is constant independent of the size of the input string, the space complexity becomes, $$O(1)$$.


Log in to reply
 

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