[剑指Offer] Day 26: String

Authored by Tony Feng

Created on May 7th, 2022

Last Modified on May 7th, 2022

Task 1 - Q20. 表示数值的字符串

Question

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：

若干空格
一个小数或者整数
（可选）一个 ’e’ 或 ‘E’ ，后面跟着一个整数
若干空格

小数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（’+’ 或 ‘-’）
下述格式之一：
- 至少一位数字，后面跟着一个点 ‘.’
- 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
- 一个点 ‘.’ ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（’+’ 或 ‘-’）
至少一位数字

部分数值列举如下： ["+100", “5e2”, “-123”, “3.1416”, “-1E-16”, “0123”]

部分非数值列举如下： [“12e”, “1a3.14”, “1.2.3”, “+-5”, “12e+5.4”]

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution: # State Machine
    def isNumber(self, s: str) -> bool:
        states = [
            { ' ': 0, 's': 1, 'd': 2, '.': 4 }, # 0. start with 'blank'
            { 'd': 2, '.': 4 } ,                # 1. 'sign' before 'e'
            { 'd': 2, '.': 3, 'e': 5, ' ': 8 }, # 2. 'digit' before 'dot'
            { 'd': 3, 'e': 5, ' ': 8 },         # 3. 'digit' after 'dot'
            { 'd': 3 },                         # 4. 'digit' after 'dot' (‘blank’ before 'dot')
            { 's': 6, 'd': 7 },                 # 5. 'e'
            { 'd': 7 },                         # 6. 'sign' after 'e'
            { 'd': 7, ' ': 8 },                 # 7. 'digit' after 'e'
            { ' ': 8 }                          # 8. end with 'blank'
        ]
        p = 0                           # start with state 0
        for c in s:
            if '0' <= c <= '9': t = 'd' # digit
            elif c in "+-": t = 's'     # sign
            elif c in "eE": t = 'e'     # e or E
            elif c in ". ": t = c       # dot, blank
            else: t = '?'               # unknown
            if t not in states[p]: return False
            p = states[p][t] # Use hash map to transfer the state
        return p in (2, 3, 7, 8)

Explanation

State Machine

Time Complexity: O(N)
Space Complexity: O(1)

Task 2 - Q67. 把字符串转换成整数

Question

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面所欲=有连续数字组合起来，作为该整数的正负号。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
我们只能存储 32 位大小的有符号整数[−2147483648, 2147483647]。
如果数值超过这个范围，请返回 INT_MAX ( 2³¹ − 1) 或 INT_MIN (−2³¹) 。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution:
    def strToInt(self, str: str) -> int:
        if not str: return 0

        # Ignore the spaces
        i = 0
        while i < len(str) and str[i] == " ":
            i += 1
        if i == len(str): # str consist of spaces
            return 0

        ans = 0
        sign = -1 if str[i] == '-' else 1
        if str[i] in ['+', '-']: # Move to next position
            i += 1 

        intMax, intMin, lmt = 2**31 - 1, -2**31, 2**31//10 # 214748364
        for c in str[i:]:
            if not '0' <= c <= '9': # not a number
                break

            if ans > lmt or (ans == lmt and c > '7'):
                return intMax if sign == 1 else intMin
            else:
                ans = 10 * ans + (ord(c) - ord('0')) # The difference of ASCII
        return sign * ans

Explanation

Time Complexity: O(N)
Space Complexity: O(1)