[面试题] 算法面试题：数值字符串的三种解法详解（正则、状态机、暴力拆解）

请实现一个函数用来判断字符串 str 是否表示数值（包括科学计数法的数字，小数和整数）。

根据题目定义，一个合法的数值字符串（包含科学计数法）按顺序应包含以下部分：

1. 若干空格
2. 一个整数或小数
3. （可选）一个 'e' 或 'E' ，后面跟着一个整数（可正可负）
4. 若干空格

其中，小数的格式可以是以下几种之一：

• 至少一位数字，后面跟着一个点 '.'
• 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
• 一个点 '.' ，后面跟着至少一位数字

整数的格式为：

• 若干空格
• （可选）一个符号字符（'+' 或 '-'）
• 至少一位数字
• 若干空格

示例说明：

• ["+100","5e2","-123","3.1416","-1E-16"] 都是数值。
• ["12e","1a3.14","1.2.3","+-5","12e+4.3"] 都不是数值。

提示:

1. 1 <= str.length <= 25
2. str 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，空格 ' ' 或者点 '.' 。

解题思路分析与实现

本题的核心在于严谨地处理所有可能的字符序列和状态。下面介绍三种主流的解法。

方法一：暴力分析拆解（条件判断法）

此方法通过维护几个布尔状态变量，在遍历字符串时根据当前字符进行条件判断。

核心思路：
定义四个状态变量：

• hasNum: 是否已经出现过数字。
• hasE: 是否已经出现过 'E' 或 'e'。
• hasSign: 是否已经出现过符号 ('+'/'-')。
• hasDot: 是否已经出现过小数点 '.'。

遍历字符串，依据以下规则进行判断：

1. 数字：遇到数字，标记 hasNum = true，索引后移。
2. e/E：如果前面已经出现过 E 或者前面没有数字(!hasNum)，非法。否则，hasE 置为 true，并重置 hasNum, hasSign, hasDot 为 false（因为指数部分可以看作一个新的数字开始）。
3. 符号 (+/-)：如果符号已经出现过，或者前面已经出现过数字或小数点，非法。否则，hasSign 置为 true。
4. 小数点 (.)：如果小数点已经出现过，或者已经出现过 E，非法。否则，hasDot 置为 true。
5. 空格 ( )：遇到空格直接跳出循环（后续再处理结尾空格）。
6. 其他字符：直接返回 false。

遍历结束后，需要跳过末尾的空格。最终合法的条件是：索引到达字符串末尾，且整个过程中出现过数字 (hasNum == true)。

public boolean isNumeric(String str) {
    int size = str.length();
    int index = 0;
    // 初始化状态变量
    boolean hasNum = false, hasE = false, hasSign = false, hasDot = false;
    // 跳过开头空格
    while (index < size && str.charAt(index) == ' ') {
        index++;
    }

    while (index < size) {
        // 处理连续数字
        while (index < size && str.charAt(index) >= '0' && str.charAt(index) <= '9') {
            index++;
            hasNum = true;
        }
        // 如果已经到末尾，跳出主循环
        if (index == size) {
            break;
        }

        char c = str.charAt(index);
        if (c == 'e' || c == 'E') {
            // E前面必须有数字，且不能已经出现过E
            if (hasE || !hasNum) {
                return false;
            }
            hasE = true;
            // 重置状态，E后面可以接符号、数字和小数点(但E后不能有小数点，会被后续规则判断)
            hasNum = false;
            hasSign = false;
            hasDot = false;
        } else if (c == '+' || c == '-') {
            // 符号不能在数字、小数点或另一个符号之后出现
            if (hasSign || hasNum || hasDot) {
                return false;
            }
            hasSign = true;
        } else if (c == '.') {
            // 小数点不能重复出现，也不能出现在E之后
            if (hasDot || hasE) {
                return false;
            }
            hasDot = true;
        } else if (c == ' ') {
            // 遇到空格，跳出循环去处理结尾空格
            break;
        } else {
            // 非法字符
            return false;
        }
        index++;
    }
    // 跳过结尾空格
    while (index < size && str.charAt(index) == ' ') {
        index++;
    }
    // 最终判断：必须遍历完所有字符，且整个字符串中有数字
    return hasNum && index == size;
}

复杂度分析：

• 时间复杂度：O(n)，需要遍历字符串一次。
• 空间复杂度：O(1)，只使用了常数个变量。

方法二：正则表达式匹配

对于这类模式固定的字符串处理问题，正则表达式提供了一种非常简洁的解决方案。虽然面试中可能不是考察重点，但在实际工程中很实用。

核心正则表达式：

^\s*[+-]?(\d*\.\d+|\d+(\.\d*)?)(?:[eE][+-]?\d+)?\s*$

表达式分解：

• ^\s*：匹配开头0个或多个空格。
• [+-]?：匹配0个或1个正负号。
• (\d*\.\d+|\d+(\.\d*)?)：匹配小数部分。这是关键，它匹配两种格式：
  • \d*\.\d+：例如 .1、0.1、123.4
  • \d+(\.\d*)?：例如 1、1.、123.
• (?:[eE][+-]?\d+)?：非捕获分组，匹配可选的指数部分。例如 e10、E-5。
• \s*$：匹配结尾0个或多个空格。

import java.util.regex.Pattern;

public class Solution {
    public boolean isNumeric (String str) {
        // 核心正则表达式
        String pattern = "^\\s*[+-]?(\\d*\\.\\d+|\\d+(\\.\\d*)?)(?:[eE][+-]?\\d+)?\\s*$";
        return Pattern.matches(pattern, str);
    }
}

复杂度分析：

• 时间复杂度：O(n)，正则引擎需要扫描字符串。
• 空间复杂度：O(1)。

方法三：有限状态机 (DFA)

有限状态机(DFA) 是解决此类复杂格式验证问题的经典且严谨的方法。它通过定义一组“状态”和基于输入字符的“状态转移规则”来精确建模整个判断流程。

状态定义：
我们定义9种状态：

• 0: 起始空格
• 1: 符号位 (+/-)
• 2: 整数部分数字
• 3: 小数点（前面无数字）
• 4: 小数点（后面有数字）
• 5: 指数符号 e/E
• 6: 指数部分的符号位
• 7: 指数部分的数字
• 8: 结尾空格

状态转移：
根据当前状态和输入的字符类型（空格、符号、数字、小数点、e/E、非法字符），查找预定义的状态转移表，决定下一个状态。如果转移到的状态为 -1，则说明输入非法。

public boolean isNumberDFA(String str) {
    if (str == null) return false;

    // 状态定义：0-8
    int state = 0; // 初始状态：起始空格

    // 状态转移表 [当前状态][输入类型] -> 下一状态
    int[][] transitionTable = {
        // 输入类型: 空格(0) 符号(1) 数字(2) 小数点(3) e/E(4) 其他(5)
        {0,         1,       2,       3,      -1,    -1}, // 状态0: 起始空格
        {-1,       -1,       2,       3,      -1,    -1}, // 状态1: 符号
        {8,        -1,       2,       4,       5,    -1}, // 状态2: 整数数字
        {-1,       -1,       4,      -1,      -1,    -1}, // 状态3: 小数点前无数字
        {8,        -1,       4,      -1,       5,    -1}, // 状态4: 小数点后有数字
        {-1,        6,       7,      -1,      -1,    -1}, // 状态5: 指数e
        {-1,       -1,       7,      -1,      -1,    -1}, // 状态6: 指数符号
        {8,        -1,       7,      -1,      -1,    -1}, // 状态7: 指数数字
        {8,        -1,      -1,      -1,      -1,    -1}  // 状态8: 结尾空格
    };

    for (char c : str.toCharArray()) {
        int inputType = getInputType(c);
        if (inputType == -1) return false; // 非法字符

        state = transitionTable[state][inputType];
        if (state == -1) return false; // 非法状态转移
    }

    // 可接受的终止状态：必须是有效的数字结尾状态
    // 状态2（纯整数），状态4（小数），状态7（指数数字），状态8（数字后接空格）
    return state == 2 || state == 4 || state == 7 || state == 8;
}

// 将输入字符映射为状态机输入类型
private int getInputType(char c) {
    switch (c) {
        case ' ': return 0; // 空格
        case '+':
        case '-': return 1; // 符号
        case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
            return 2; // 数字
        case '.': return 3; // 小数点
        case 'e':
        case 'E': return 4; // 指数符号
        default: return 5; // 其他非法字符
    }
}

复杂度分析：

• 时间复杂度：O(n)，遍历字符串一次。
• 空间复杂度：O(1)，状态转移表大小固定。

总结

1. 暴力拆解法：逻辑直观，通过维护多个布尔标志和条件分支实现，易于理解和手写，是面试中的常见解法。
2. 正则表达式法：代码最简洁，适合对正则熟悉且在工程中快速实现验证的场景，但可能不是算法面试考察的重点。
3. 有限状态机(DFA)法：最为严谨和模块化，能清晰地描绘出所有合法路径，是处理复杂格式验证问题的通用且强大的方法，体现了良好的算法设计思想。

三种方法各有优劣，理解其背后的逻辑对于提升字符串处理和问题建模能力大有裨益。