65. 有效数字

题目描述

输入字符串 s，判断它能否表示一个合法的数，能则返回 true，否则返回 false。

合法的数由两部分依次组成：先是一个整数或一个小数，后面可以再接一个指数部分，也可以不接。

整数：开头可带一个 + 或 -，之后是至少一位数字。小数：开头同样可带一个符号，之后是三种形式之一：数字加小数点（如 4.）、数字加小数点再加数字（如 3.14）、小数点加数字（如 .9）。也就是说，小数点两边至少有一边有数字。

指数部分：一个 e 或 E，后面紧跟一个整数（可带符号）。

例如 "2"、"0089"、"-.9"、"3e+7"、"53.5e93" 都合法；"abc"、"1e"、"e3"、"99e2.5"、"--6" 都不合法。

示例 1

输入：s = "0"
输出：true

解释：单个数字 0 是合法整数。

示例 2

输入：s = "e"
输出：false

解释：只有指数符号，前后都缺少数字。

示例 3

输入：s = "."
输出：false

解释：只有小数点，两边都没有数字。

数据范围

1 <= s.length <= 20
s 只含大小写英文字母、数字 0-9、+、- 和 .。

解题思路：标志位一次扫描

一次扫描，用三个标记记录状态：seen_digit（当前这一部分见过数字）、seen_dot（见过小数点）、seen_exp（见过 e）。规则：符号只能出现在开头或紧跟 e 之后；e 只能出现一次，且前面必须有数字，遇到 e 后把 seen_digit 重置为 False，要求指数部分重新出现数字；小数点只能出现一次，且不能在 e 之后；其它字符一律非法。扫完后返回 seen_digit，确保最后一部分有数字。

为什么正确

扫完 s[:i] 而未提前返回，表示 s[:i] 是某个有效数字的前缀；它本身是否有效，取决于 seen_digit。

复杂度分析

时间 O(n)；空间 O(1)。

易错点

遇到 e 后一定要把 seen_digit 重置为 False，否则 "1e" 会被误判为有效；只有一个 "."、"+." 这类没有数字的串要靠最后返回 seen_digit 来拦住。e 后面的指数必须是整数，所以 e 后不能再出现小数点。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def isNumber(self, s: str) -> bool:
        seen_digit = seen_dot = seen_exp = False
        for i, c in enumerate(s):
            if c.isdigit():
                seen_digit = True
            elif c in '+-':
                if i > 0 and s[i - 1] not in 'eE':
                    return False
            elif c in 'eE':
                if seen_exp or not seen_digit:
                    return False
                seen_exp = True
                seen_digit = False
            elif c == '.':
                if seen_dot or seen_exp:
                    return False
                seen_dot = True
            else:
                return False
        return seen_digit

class Solution {
    public boolean isNumber(String s) {
        boolean seenDigit = false, seenDot = false, seenExp = false;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                seenDigit = true;
            } else if (c == '+' || c == '-') {
                if (i > 0 && s.charAt(i - 1) != 'e' && s.charAt(i - 1) != 'E') {
                    return false;
                }
            } else if (c == 'e' || c == 'E') {
                if (seenExp || !seenDigit) {
                    return false;
                }
                seenExp = true;
                seenDigit = false;
            } else if (c == '.') {
                if (seenDot || seenExp) {
                    return false;
                }
                seenDot = true;
            } else {
                return false;
            }
        }
        return seenDigit;
    }
}

class Solution {
public:
    bool isNumber(string s) {
        bool seenDigit = false, seenDot = false, seenExp = false;
        for (int i = 0; i < (int)s.size(); i++) {
            char c = s[i];
            if (isdigit((unsigned char)c)) {
                seenDigit = true;
            } else if (c == '+' || c == '-') {
                if (i > 0 && s[i - 1] != 'e' && s[i - 1] != 'E') {
                    return false;
                }
            } else if (c == 'e' || c == 'E') {
                if (seenExp || !seenDigit) {
                    return false;
                }
                seenExp = true;
                seenDigit = false;
            } else if (c == '.') {
                if (seenDot || seenExp) {
                    return false;
                }
                seenDot = true;
            } else {
                return false;
            }
        }
        return seenDigit;
    }
};

func isNumber(s string) bool {
	seenDigit, seenDot, seenExp := false, false, false
	for i := 0; i < len(s); i++ {
		c := s[i]
		if c >= '0' && c <= '9' {
			seenDigit = true
		} else if c == '+' || c == '-' {
			if i > 0 && s[i-1] != 'e' && s[i-1] != 'E' {
				return false
			}
		} else if c == 'e' || c == 'E' {
			if seenExp || !seenDigit {
				return false
			}
			seenExp = true
			seenDigit = false
		} else if c == '.' {
			if seenDot || seenExp {
				return false
			}
			seenDot = true
		} else {
			return false
		}
	}
	return seenDigit
}

var isNumber = function(s) {
    let seenDigit = false, seenDot = false, seenExp = false;
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (c >= '0' && c <= '9') {
            seenDigit = true;
        } else if (c === '+' || c === '-') {
            if (i > 0 && s[i - 1] !== 'e' && s[i - 1] !== 'E') {
                return false;
            }
        } else if (c === 'e' || c === 'E') {
            if (seenExp || !seenDigit) {
                return false;
            }
            seenExp = true;
            seenDigit = false;
        } else if (c === '.') {
            if (seenDot || seenExp) {
                return false;
            }
            seenDot = true;
        } else {
            return false;
        }
    }
    return seenDigit;
};

function isNumber(s: string): boolean {
    let seenDigit = false, seenDot = false, seenExp = false;
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (c >= '0' && c <= '9') {
            seenDigit = true;
        } else if (c === '+' || c === '-') {
            if (i > 0 && s[i - 1] !== 'e' && s[i - 1] !== 'E') {
                return false;
            }
        } else if (c === 'e' || c === 'E') {
            if (seenExp || !seenDigit) {
                return false;
            }
            seenExp = true;
            seenDigit = false;
        } else if (c === '.') {
            if (seenDot || seenExp) {
                return false;
            }
            seenDot = true;
        } else {
            return false;
        }
    }
    return seenDigit;
}

载入编辑器，自己跑一遍 →

其他解法

标志位写法代码短，但规则分散在多处 if 判断中，容易漏掉边界；自动机把所有规则整理成转移表，更系统、更不容易出错，两者复杂度相同。

解法 2：确定有限状态自动机时间 O(n)，空间 O(1)

把字符分成四类：数字、正负号、小数点、e/E。再定义 9 个状态：起始、符号位、整数部分、整数后的小数点、前面无整数的小数点、小数部分、指数符号 e、指数的正负号、指数数字。用一张状态转移表描述每个状态读到每类字符后去哪里，-1 表示非法。逐个字符转移，读完后状态属于整数部分、整数后的小数点、小数部分、指数数字之一，就是合法数字。

规则都集中在转移表里，正确性容易逐格检查，修改规则只需改表。缺点是要先设计好状态，表本身不如标志位直观。

class Solution:
    def isNumber(self, s: str) -> bool:
        # 字符类别：0 数字，1 符号，2 小数点，3 指数符号 e/E
        # 状态：0 起始，1 符号，2 整数，3 整数后的点，4 无整数的点
        #       5 小数部分，6 e，7 指数符号，8 指数数字
        trans = [
            [2, 1, 4, -1],
            [2, -1, 4, -1],
            [2, -1, 3, 6],
            [5, -1, -1, 6],
            [5, -1, -1, -1],
            [5, -1, -1, 6],
            [8, 7, -1, -1],
            [8, -1, -1, -1],
            [8, -1, -1, -1],
        ]
        state = 0
        for c in s:
            if '0' <= c <= '9':
                t = 0
            elif c in '+-':
                t = 1
            elif c == '.':
                t = 2
            elif c in 'eE':
                t = 3
            else:
                return False
            state = trans[state][t]
            if state < 0:
                return False
        return state in (2, 3, 5, 8)

class Solution {
    public boolean isNumber(String s) {
        int[][] trans = {
            {2, 1, 4, -1},
            {2, -1, 4, -1},
            {2, -1, 3, 6},
            {5, -1, -1, 6},
            {5, -1, -1, -1},
            {5, -1, -1, 6},
            {8, 7, -1, -1},
            {8, -1, -1, -1},
            {8, -1, -1, -1},
        };
        int state = 0;
        for (char c : s.toCharArray()) {
            int t;
            if (c >= '0' && c <= '9') t = 0;
            else if (c == '+' || c == '-') t = 1;
            else if (c == '.') t = 2;
            else if (c == 'e' || c == 'E') t = 3;
            else return false;
            state = trans[state][t];
            if (state < 0) return false;
        }
        return state == 2 || state == 3 || state == 5 || state == 8;
    }
}

class Solution {
public:
    bool isNumber(string s) {
        int trans[9][4] = {
            {2, 1, 4, -1},
            {2, -1, 4, -1},
            {2, -1, 3, 6},
            {5, -1, -1, 6},
            {5, -1, -1, -1},
            {5, -1, -1, 6},
            {8, 7, -1, -1},
            {8, -1, -1, -1},
            {8, -1, -1, -1},
        };
        int state = 0;
        for (char c : s) {
            int t;
            if (c >= '0' && c <= '9') t = 0;
            else if (c == '+' || c == '-') t = 1;
            else if (c == '.') t = 2;
            else if (c == 'e' || c == 'E') t = 3;
            else return false;
            state = trans[state][t];
            if (state < 0) return false;
        }
        return state == 2 || state == 3 || state == 5 || state == 8;
    }
};

func isNumber(s string) bool {
	trans := [9][4]int{
		{2, 1, 4, -1},
		{2, -1, 4, -1},
		{2, -1, 3, 6},
		{5, -1, -1, 6},
		{5, -1, -1, -1},
		{5, -1, -1, 6},
		{8, 7, -1, -1},
		{8, -1, -1, -1},
		{8, -1, -1, -1},
	}
	state := 0
	for i := 0; i < len(s); i++ {
		c := s[i]
		var t int
		switch {
		case c >= '0' && c <= '9':
			t = 0
		case c == '+' || c == '-':
			t = 1
		case c == '.':
			t = 2
		case c == 'e' || c == 'E':
			t = 3
		default:
			return false
		}
		state = trans[state][t]
		if state < 0 {
			return false
		}
	}
	return state == 2 || state == 3 || state == 5 || state == 8
}

var isNumber = function(s) {
    const trans = [
        [2, 1, 4, -1],
        [2, -1, 4, -1],
        [2, -1, 3, 6],
        [5, -1, -1, 6],
        [5, -1, -1, -1],
        [5, -1, -1, 6],
        [8, 7, -1, -1],
        [8, -1, -1, -1],
        [8, -1, -1, -1],
    ];
    let state = 0;
    for (const c of s) {
        let t;
        if (c >= '0' && c <= '9') t = 0;
        else if (c === '+' || c === '-') t = 1;
        else if (c === '.') t = 2;
        else if (c === 'e' || c === 'E') t = 3;
        else return false;
        state = trans[state][t];
        if (state < 0) return false;
    }
    return state === 2 || state === 3 || state === 5 || state === 8;
};

function isNumber(s: string): boolean {
    const trans: number[][] = [
        [2, 1, 4, -1],
        [2, -1, 4, -1],
        [2, -1, 3, 6],
        [5, -1, -1, 6],
        [5, -1, -1, -1],
        [5, -1, -1, 6],
        [8, 7, -1, -1],
        [8, -1, -1, -1],
        [8, -1, -1, -1],
    ];
    let state = 0;
    for (const c of s) {
        let t: number;
        if (c >= '0' && c <= '9') t = 0;
        else if (c === '+' || c === '-') t = 1;
        else if (c === '.') t = 2;
        else if (c === 'e' || c === 'E') t = 3;
        else return false;
        state = trans[state][t];
        if (state < 0) return false;
    }
    return state === 2 || state === 3 || state === 5 || state === 8;
}

字符串专题的其他题目

查看字符串全部题目 →