657 Judge Route Circle

657. Judge Route Circle

1. Question

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 areR(Right),L(Left),U(Up) andD(down). The output should be true or false representing whether the robot makes a circle.

Example 1:

Input: "UD"

Output: true

Example 2:

Input: "LL"

Output: false

2. Implementation

(1) Intuition

class Solution {
    public boolean judgeCircle(String moves) {
        int horizontalMove = 0, verticalMove = 0;

        for (char move : moves.toCharArray()) {
            switch(move) {
                case 'U': 
                    --verticalMove;
                    break;
                case 'D': 
                    ++verticalMove;
                    break;
                case 'L': 
                    --horizontalMove;
                    break;
                case 'R': 
                    ++horizontalMove;
                    break;
            }
        }

        return horizontalMove == 0 && verticalMove == 0;
    }
}

(2) HashMap

class Solution {
    public boolean judgeCircle(String moves) {
        Map<Character, Integer> map = new HashMap<>();

        map.put('U', -1);
        map.put('D', 1);
        map.put('L', -2);
        map.put('R', 2);

        int offset = 0;

        for (char c : moves.toCharArray()) {
            offset += map.get(c);
        }

        return offset == 0;
    }
}

3. Time & Space Complexity

Intuition: 时间复杂度O(n), 空间复杂度O(1)

HashMap: 时间复杂度O(n), 空间复杂度O(n)