Welcome to Subscribe On Youtube

Question

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

Given a string num which represents an integer, return true if num is a strobogrammatic number.

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

 

Example 1:

Input: num = "69"
Output: true

Example 2:

Input: num = "88"
Output: true

Example 3:

Input: num = "962"
Output: false

 

Constraints:

• 1 <= num.length <= 50
• num consists of only digits.
• num does not contain any leading zeros except for zero itself.

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
• C++
• Python
• Go

• 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;
          }
      }
  
  }
  
  ############
  
  class Solution {
      public boolean isStrobogrammatic(String num) {
          int[] d = new int[] {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
          for (int i = 0, j = num.length() - 1; i <= j; ++i, --j) {
              int a = num.charAt(i) - '0', b = num.charAt(j) - '0';
              if (d[a] != b) {
                  return false;
              }
          }
          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
  
  ############
  
  class Solution:
      def isStrobogrammatic(self, num: str) -> bool:
          d = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6] # index ==> value, eg. last one, index=9 val=6
          i, j = 0, len(num) - 1
          while i <= j:
              a, b = int(num[i]), int(num[j])
              if d[a] != b:
                  return False
              i, j = i + 1, j - 1
          return True
  
  

• func isStrobogrammatic(num string) bool {
  	d := []int{0, 1, -1, -1, -1, -1, 9, -1, 8, 6}
  	for i, j := 0, len(num)-1; i <= j; i, j = i+1, j-1 {
  		a, b := int(num[i]-'0'), int(num[j]-'0')
  		if d[a] != b {
  			return false
  		}
  	}
  	return true
  }
  

All Problems

All Solutions