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

  • 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