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;
            }
        }
    
    }
    
  • // OJ: https://leetcode.com/problems/strobogrammatic-number/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    private:
        bool same(char a, char b) {
            return a == b && (a == '0' || a == '1' || a == '8');
        }
        bool match(char a, char b) {
            if (a > b) swap(a, b);
            return same(a, b) || (a == '6' && b == '9');
        }
    public:
        bool isStrobogrammatic(string num) {
            int i = 0, j = num.size() - 1;
            for (; i <= j; ++i, --j) {
                if ((i != j && !match(num[i], num[j]))
                   || (i == j && !same(num[i], num[j]))) return false;
            }
            return true;
        }
    };
    
  • class Solution(object):
      def isStrobogrammatic(self, num):
        """
        :type num: str
        :rtype: bool
        """
        start, end, legal = 0, len(num) - 1, "01689"
        while start <= end:
          if "".join(sorted(num[start] + num[end])) not in ["00", "11", "88", "69"]:
            return False
          start += 1
          end -= 1
        return True
    
    

All Problems

All Solutions