Google
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:
1
Input: "UD"
2
3
Output: true
Copied!
Example 2:
1
Input: "LL"
2
3
Output: false
Copied!

2. Implementation

(1) Intuition
1
class Solution {
2
public boolean judgeCircle(String moves) {
3
int horizontalMove = 0, verticalMove = 0;
4
5
for (char move : moves.toCharArray()) {
6
switch(move) {
7
case 'U':
8
--verticalMove;
9
break;
10
case 'D':
11
++verticalMove;
12
break;
13
case 'L':
14
--horizontalMove;
15
break;
16
case 'R':
17
++horizontalMove;
18
break;
19
}
20
}
21
22
return horizontalMove == 0 && verticalMove == 0;
23
}
24
}
Copied!
(2) HashMap
1
class Solution {
2
public boolean judgeCircle(String moves) {
3
Map<Character, Integer> map = new HashMap<>();
4
5
map.put('U', -1);
6
map.put('D', 1);
7
map.put('L', -2);
8
map.put('R', 2);
9
10
int offset = 0;
11
12
for (char c : moves.toCharArray()) {
13
offset += map.get(c);
14
}
15
16
return offset == 0;
17
}
18
}
Copied!

3. Time & Space Complexity

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