Solution by vinnyoodles


  • 3
    V

    Approach #1 Iterative [Accepted]

    Intuition

    Keep track of the current coordinate and compare the final coordinate to the initial coordinate.

    Algorithm

    The initial coordinate is (0, 0). If we visualize the initial coordinate as the origin in the coordinate plane, then we can give each of the four direction a vector value.

    U => +1 y
    D => -1 y
    L => -1 x
    R => +1 x
    

    The algorithm will keep track of the current coordinate for every move in the sequence of moves. For every move, the coordinate will be updated by adding the move's corresponding vector value.

    After the last move is taken into consideration, the final coordinate has been calculated. At this point, the final coordinate can be compared to the initial coordinate to determine if a circle has been completed. If the final coordinate and the initial coordinate are equivalent, then a circle has been completed.

    Java

    public class Solution {
        public boolean judgeCircle(String moves) {
            int x = 0;
            int y = 0;
            for (char c : moves.toCharArray()) {
                if (c == 'U') {
                    y ++;
                } else if (c == 'D') { 
                    y --;
                } else if (c == 'L') {
                    x --; 
                } else if (c == 'R') {
                    x ++;  
                }
            }
            
            return x == 0 && y == 0;
        }
    }
    

    Complexity Analysis

    • Time complexity: $$O(n)$$. n is the number of moves and each move must be taken into consideration to find the final coordinate.

    • Space complexity: $$O(1)$$. The only variables needed are to keep track of the current coordinate. This can be done with two integer variables which both require constant space.


Log in to reply
 

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