Question

Formatted question description: https://leetcode.ca/all/246.html

 246	Strobogrammatic Number

 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.

 Example 1:

 Input:  "69"
 Output: true
 Example 2:

 Input:  "88"
 Output: true
 Example 3:

 Input:  "962"
 Output: false

 @tag-string

Algorithm

There are actually few numbers that meet this condition, only 0,1,8,6,9.

This question can actually be regarded as a special case of finding the number of palindromes, or use double pointers to detect it.

  • If the first and last two numbers are equal, only if they are one of 0,1,8,
  • If they are not equal, one is 6 and the other is 9, or one is 9 and the other is 6.
  • All other cases return false

Code

Java

import java.util.HashMap;
import java.util.Map;

public class Strobogrammatic_Number {


    class Solution {
        public boolean isStrobogrammatic(String num) {
            Map<Character, Character> m = new HashMap<Character, Character>(){ {
                put('0', '0');
                put('1', '1');
                put('8', '8');
                put('6', '9');
                put('9', '6');
            } };

            for (int i = 0; i <= num.length() / 2; ++i) {
                if (m.get(num.charAt(i)) != num.charAt(num.length() - i - 1)) return false;
            }
            return true;

        }
    }

    class Solution_noExtraSpace {
        public boolean isStrobogrammatic(String num) {
            if (num == null || num.length() == 0) {
                return true;
            }
            if (num.length() == 1) {
                return num.equals("0") || num.equals("1") || num.equals("8");
            }

            int l = 0, r = num.length() - 1;
            while (l <= r) {
                if (num.charAt(l) == num.charAt(r)) {
                    if (num.charAt(l) != '1' && num.charAt(l) != '0' && num.charAt(l) != '8'){
                        return false;
                    }
                } else {
                    if ((num.charAt(l) != '6' || num.charAt(r) != '9') && (num.charAt(l) != '9' || num.charAt(r) != '6')) {
                        return false;
                    }
                }
                ++l; --r;
            }

            return true;
        }
    }

}

All Problems

All Solutions