246.Strobogrammatic Number

Tags: [string], [two_pointer], [map]

Com: {g}

Link: https://leetcode.com/problems/strobogrammatic-number/\#/description

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.

Solution: Two Pointer, Map

class Solution(object):
    def isStrobogrammatic(self, num):
        """
        :type num: str
        :rtype: bool
        """
        if not num:
            return True

        size = len(num)
        if size % 2 != 0:
            mid = num[size / 2]
            if not (mid == '0' or mid == '1' or mid == '8'):
                return False

        char_map = {
            '0': '0',
            '1': '1',
            '6': '9',
            '8': '8',
            '9': '6'
        }

        left = 0
        right = size - 1
        while left < right:
            if num[left] not in char_map or\
               num[right] not in char_map or\
               char_map[num[left]] != num[right]:
                   return False

            left += 1
            right -= 1

        return True

Revelation:

• If the number of chars is odd, we should check the mid char.

Note:

• Time complexity = O(n), n is the length of the given string.
• Space complexity = O(1).