Judge Route Circle

• LeetCode: Judge Route Circle
• Problem:

Initially, there is a Robot at position (0, 0). 

Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.

The move sequence is represented by a string. 

And each move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). 

The output should be true or false representing whether the robot makes a circle.

• Example1:

Input: "UD"
Output: true

• Example2:

Input: "LL"
Output: false

• Analysis:

According to the problem description, the route circle is defined that it moves back to the original place (0, 0).

What we do is that go over all moves and judge the final position is (0, 0).

• Code - Java:

class Solution {
    public boolean judgeCircle(String moves) {
        int len = moves.length();
        if (len == 0) {
            return false;
        }
        int x = 0; 
        int y = 0;
        for (int i = 0; i < len; i++) {
            char direct = moves.charAt(i);
            if (direct == 'U') {
                y++;
            } else if (direct == 'D') {
                y--;
            } else if (direct == 'L') {
                x--;
            } else if (direct == 'R') {
                x++;
            }
        }
        return x == 0 && y == 0;
    }
}

• Code - C++:

class Solution {
public:
    bool judgeCircle(string moves) {
        int len = moves.length();
        int x = 0;
        int y = 0;
        for (int i = 0; i < len; i++) {
            char direct = moves[i];
            if (direct == 'U') {
                y++;
            } else if (direct == 'D') {
                y--;
            } else if (direct == 'L') {
                x--;
            } else if (direct == 'R') {
                x++;
            }
        }
        return x == 0 && y == 0;
    }
};

• Code - Python:

class Solution(object):
    def judgeCircle(self, moves):
        """
        :type moves: str
        :rtype: bool
        """
        x,y = 0, 0
        for direct in moves:
            if direct == 'U':
                y += 1
            elif direct == 'D':
                y -= 1
            elif direct == 'L':
                x -= 1
            elif direct == 'R':
                x += 1
        return x == 0 and y == 0

• Code - C:

bool judgeCircle(char* moves) {
    int x = 0;
    int y = 0;
    for (int i = 0;; i++) {
        if (moves[i] == '\0') {
            break;
        }
        if (moves[i] == 'U') {
            y++;
        } else if (moves[i] == 'D') {
            y--;
        } else if (moves[i] == 'L') {
            x--;
        } else if (moves[i] == 'R') {
            x++;
        }
    }
    return x == 0 && y == 0;
}

• Time Complexity : O(N), N is length of input string.
• Space Complexity: O(1)