LeetCode 题目 66：加一【python5种算法实现】

题目描述

验证给定的字符串是否可以解释为十进制数字。

例如:

“0” => true
“0.1” => true
“abc” => false
“1 a” => false
“2e10” => true
" -90e3 " => true
" 1e" => false
“e3” => false
" 6e-1" => true
" 99e2.5 " => false
“53.5e93” => true
" --6 " => false
“-+3” => false
“95a54e53” => false

说明: 我们考虑在 ASCII 字符集中的空白字符，非负整数和小数。

输入格式

s：一个字符串。

输出格式

返回一个布尔值，表示是否为有效的十进制数字。

方法一：有限状态自动机（Finite State Automaton, FSA）

解题步骤

定义状态：创建状态转换表，包括接受数字、符号、小数点、指数符号等状态。
初始化状态：初始状态设定为 start。
状态转移：根据当前字符和状态转换表更新状态。
终止检查：最终状态在接受状态集合中，则返回 true；否则返回 false。

完整的规范代码

def isNumber(s):
    """
    使用有限状态自动机（FSA）方法判断字符串是否为有效的十进制数字
    :param s: str, 输入字符串
    :return: bool, 是否为有效的十进制数字
    """
    state = 0
    finals = [0, 0, 0, 1, 0, 1, 1, 0, 1]  # 有效终止状态
    transitionTable = [
        [0, 1, 6, 2, -1, -1],   # state 0
        [-1, -1, 6, 2, -1, -1],  # state 1
        [-1, -1, 3, -1, -1, -1], # state 2
        [8, -1, 3, -1, 4, -1],   # state 3
        [-1, 7, 5, -1, -1, -1],  # state 4
        [8, -1, 5, -1, -1, -1],  # state 5
        [8, -1, 6, 3, 4, -1],    # state 6
        [-1, -1, 5, -1, -1, -1], # state 7
        [8, -1, -1, -1, -1, -1]  # state 8
    ]
    # Input classes: [invalid, '+/-', 'number', '.', 'e/E', 'other']
    def inputType(c):
        if c == ' ':
            return 0
        if c in '+-':
            return 1
        if c.isdigit():
            return 2
        if c == '.':
            return 3
        if c in 'eE':
            return 4
        return 5

    for c in s.strip():
        state = transitionTable[state][inputType(c)]
        if state == -1:
            return False
    return finals[state] == 1

# 示例调用
print(isNumber("0"))  # 输出: True
print(isNumber("0.1"))  # 输出: True
print(isNumber("abc"))  # 输出: False
print(isNumber("1 a"))  # 输出: False
print(isNumber("2e10"))  # 输出: True
print(isNumber(" -90e3 "))  # 输出: True
print(isNumber("1e"))  # 输出: False
print(isNumber("e3"))  # 输出: False
print(isNumber("6e-1"))  # 输出: True
print(isNumber("99e2.5"))  # 输出: False
print(isNumber("53.5e93"))  # 输出: True
print(isNumber("--6"))  # 输出: False
print(isNumber("-+3"))  # 输出: False
print(isNumber("95a54e53"))  # 输出: False

算法分析

时间复杂度：(O(n))，只需要遍历字符串一次。
空间复杂度：(O(1))，状态转换表的大小是常数。

方法二：正则表达式

解题步骤

定义正则表达式：使用正则表达式匹配可能的数字模式。
模式匹配：使用 Python 的 re 模块来检查字符串是否符合定义的正则表达式。

完整的规范代码

import re

def isNumber(s):
    """
    使用正则表达式判断字符串是否为有效的十进制数字
    :param s: str, 输入字符串
    :return: bool, 是否为有效的十进制数字
    """
    pattern = r'^[+-]?(\d+(\.\d*)?|\.\d+)([eE][+-]?\d+)?$'
    return re.match(pattern, s.strip()) is not None

# 示例调用
print(isNumber("0"))  # 输出: True
print(isNumber("0.1"))  # 输出: True
print(isNumber("abc"))  # 输出: False
print(isNumber("1 a"))  # 输出: False
print(isNumber("2e10"))  # 输出: True
print(isNumber(" -90e3 "))  # 输出: True
print(isNumber("1e"))  # 输出: False
print(isNumber("e3"))  # 输出: False
print(isNumber("6e-1"))  # 输出: True
print(isNumber("99e2.5"))  # 输出: False
print(isNumber("53.5e93"))  # 输出: True
print(isNumber("--6"))  # 输出: False
print(isNumber("-+3"))  # 输出: False
print(isNumber("95a54e53"))  # 输出: False

算法分析

时间复杂度：(O(n))，正则表达式的匹配时间通常与字符串长度线性相关。
空间复杂度：(O(1))，正则表达式的空间占用是常数。

方法三：分情况讨论

解题步骤

逐字符分析：逐个分析字符串中的字符，根据数字、小数点、指数部分、符号等进行分类处理。
状态标记：使用标志位记录是否出现过数字、小数点、指数等，以正确处理各种情况。

完整的规范代码

def isNumber(s):
    """
    分情况讨论法判断字符串是否为有效的十进制数字
    :param s: str, 输入字符串
    :return: bool, 是否为有效的十进制数字
    """
    s = s.strip()
    if not s:
        return False
    
    numeric = False
    decimal = False
    exponent = False
    i = 0
    
    # 处理符号
    if s[0] in "+-":
        i += 1
    
    while i < len(s):
        if s[i].isdigit():
            numeric = True
        elif s[i] == '.':
            if decimal or exponent:
                return False
            decimal = True
        elif s[i] in "eE":
            if exponent or not numeric:
                return False
            exponent = True
            numeric = False  # 需要在e之后看到数字
            decimal = False  # 防止e之后出现小数点
            if i + 1 < len(s) and s[i+1] in "+-":
                i += 1
        else:
            return False
        i += 1
    
    return numeric

# 示例调用
print(isNumber("0"))  # 输出: True
print(isNumber("0.1"))  # 输出: True
print(isNumber("abc"))  # 输出: False
print(isNumber("1 a"))  # 输出: False
print(isNumber("2e10"))  # 输出: True
print(isNumber(" -90e3 "))  # 输出: True
print(isNumber("1e"))  # 输出: False
print(isNumber("e3"))  # 输出: False
print(isNumber("6e-1"))  # 输出: True
print(isNumber("99e2.5"))  # 输出: False
print(isNumber("53.5e93"))  # 输出: True
print(isNumber("--6"))  # 输出: False
print(isNumber("-+3"))  # 输出: False
print(isNumber("95a54e53"))  # 输出: False

算法分析

时间复杂度：(O(n))，需要遍历整个字符串。
空间复杂度：(O(1))，只使用了几个辅助变量。### 方法四：逐步细化条件的处理

解题步骤

初始化变量：定义几个变量来标识数字状态，如是否遇到数字、小数点、指数等。
遍历字符串：逐字符检查，并根据字符类型（数字、小数点、指数、符号）更新状态。
后续验证：遍历结束后，根据标记的状态判断字符串是否符合数字格式。

完整的规范代码

def isNumber(s):
    """
    逐步细化条件处理法判断字符串是否为有效的十进制数字
    :param s: str, 输入字符串
    :return: bool, 是否为有效的十进制数字
    """
    s = s.strip()
    num, dot, exp, numAfterE = False, False, False, False

    for i, char in enumerate(s):
        if char.isdigit():
            num = True
            numAfterE = True
        elif char == '.':
            if dot or exp:
                return False
            dot = True
        elif char in "eE":
            if exp or not num:
                return False
            exp = True
            numAfterE = False
        elif char in "+-":
            if i > 0 and s[i-1] not in "eE":
                return False
        else:
            return False

    return num and numAfterE

# 示例调用
print(isNumber("0"))  # 输出: True
print(isNumber("0.1"))  # 输出: True
print(isNumber("abc"))  # 输出: False
print(isNumber("1 a"))  # 输出: False
print(isNumber("2e10"))  # 输出: True
print(isNumber(" -90e3 "))  # 输出: True
print(isNumber("1e"))  # 输出: False
print(isNumber("e3"))  # 输出: False
print(isNumber("6e-1"))  # 输出: True
print(isNumber("99e2.5"))  # 输出: False
print(isNumber("53.5e93"))  # 输出: True
print(isNumber("--6"))  # 输出: False
print(isNumber("-+3"))  # 输出: False
print(isNumber("95a54e53"))  # 输出: False

算法分析

时间复杂度：(O(n))，需要遍历整个字符串一次。
空间复杂度：(O(1))，使用固定数量的标记变量。

方法五：分割加验证法

解题步骤

分割处理：首先检查并处理可能的空格，然后分割处理可能的指数部分。
验证各部分：单独验证整数/小数部分和指数部分的合法性。
组合结果：确保整数/小数部分和指数部分均合法。

完整的规范代码

def isNumber(s):
    """
    分割加验证法判断字符串是否为有效的十进制数字
    :param s: str, 输入字符串
    :return: bool, 是否为有效的十进制数字
    """
    s = s.strip()
    if 'e' in s or 'E' in s:
        parts = s.split('e') if 'e' in s else s.split('E')
        if len(parts) != 2:
            return False
        left, right = parts
        return (isDecimal(left) or isInteger(left)) and isInteger(right)
    else:
        return isDecimal(s) or isInteger(s)

def isDecimal(part):
    if not part or (part[0] in '+-' and len(part) == 1):
        return False
    part = part[1:] if part[0] in '+-' else part
    dot_seen = False
    num_seen = False
    for char in part:
        if char.isdigit():
            num_seen = True
        elif char == '.':
            if dot_seen:
                return False
            dot_seen = True
        else:
            return False
    return num_seen

def isInteger(part):
    if not part:
        return False
    part = part[1:] if part[0] in '+-' else part
    return part.isdigit()

# 示例调用
print(isNumber("0"))  # 输出: True
print(isNumber("0.1"))  # 输出: True
print(isNumber("abc"))  # 输出: False
print(isNumber("1 a"))  # 输出: False
print(isNumber("2e10"))  # 输出: True
print(isNumber(" -90e3 "))  # 输出: True
print(isNumber("1e"))  # 输出: False
print(isNumber("e3"))  # 输出: False
print(isNumber("6e-1"))  # 输出: True
print(isNumber("99e2.5"))  # 输出: False
print(isNumber("53.5e93"))  # 输出: True
print(isNumber("--6"))  # 输出: False
print(isNumber("-+3"))  # 输出: False
print(isNumber("95a54e53"))  # 输出: False

算法分析

时间复杂度：(O(n))，分割和验证各部分总共需要遍历字符串一次或多次。
空间复杂度：(O(1))，除了输入字符串外，使用了有限的额外空间。

不同算法的优劣势对比

特征	方法一: FSA	方法二: 正则表达式	方法三: 分情况讨论	方法四: 逐步细化	方法五: 分割加验证
时间复杂度	(O(n))	(O(n))	(O(n))	(O(n))	(O(n))
空间复杂度	(O(1))	(O(1))	(O(1))	(O(1))	(O(1))
优势	明确状态转换，结构清晰	快速匹配，代码简洁	直观易理解，适用于多条件	状态清晰，逻辑简单	灵活处理复杂格式，模块化验证
劣势	状态表较复杂，需要细心设计	正则表达式复杂难以维护	条件多，代码冗长	多条件判断，容易出错	分割处理复杂，容易遗漏情况