Google
246 Strobogrammatic Number

1. Question

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to determine if a number is strobogrammatic. The number is represented as a string.
For example, the numbers "69", "88", and "818" are all strobogrammatic.

2. Implementation

(1) HashMap + Two Pointers
1
class Solution {
2
public boolean isStrobogrammatic(String num) {
3
Map<Character, Character> map = new HashMap<>();
4
5
map.put('0', '0');
6
map.put('1', '1');
7
map.put('6', '9');
8
map.put('8', '8');
9
map.put('9', '6');
10
11
int start = 0, end = num.length() - 1;
12
while (start <= end) {
13
if (!map.containsKey(num.charAt(start)) || map.get(num.charAt(start)) != num.charAt(end)) {
14
return false;
15
}
16
++start;
17
--end;
18
}
19
return true;
20
}
21
}
Copied!

3. Time & Space Complexity

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