LeetCode.65.有效数字（困难）

题目

LeetCode.65.有效数字（困难）

有效数字（按顺序）可以分成以下几个部分：

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

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

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

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

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

部分有效数字列举如下：

• [“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”]

部分无效数字列举如下：

• [“abc”, “1a”, “1e”, “e3”, “99e2.5”, “–6”, “-+3”, “95a54e53”]

给你一个字符串 s ，如果 s 是一个 有效数字 ，请返回 true 。

提示：

• 1 <= s.length <= 20
• s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，或者点 '.' 。

题解

解法1：正则表达式

检查字符串是不是符合某种规则，用正则表达式是最直接的想法。

怎么表示一个整数？

[+-]?\\d+

• [+-]?满足整数条件1：（可选）一个符号字符（'+' 或 '-'）。
• \\d+满足整数条件2：至少一位数字。

怎么表示一个小数？

[+-]?((\\d+\\.)|(\\d+\\.\\d+)|(\\.\\d+)

• [+-]?满足条件（可选）一个符号字符（'+' 或 '-'）。
• (\\d+\\.)满足条件至少一位数字，后面跟着一个点 '.'。
• (\\d+\\.\\d+) 满足条件至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字。
• (\\.\\d+)满足条件一个点 '.' ，后面跟着至少一位数字。

怎么表示科学计数法？

一个整数或者小数 + ([eE][+-]?\\d+)

([eE][+-]?\\d+) 满足条件一个 'e' 或 'E' ，后面跟着一个 整数，根据示例，e后面的整数前面可以带正负号。

满足题意的正则表达式？

把上面三个综合起来，就能得到最终的表达式：

([+-]?((\\d+\\.)|(\\d+\\.\\d+)|(\\.\\d+)|(\\d+)))([eE][+-]?\\d+)?

class Solution {
    fun isNumber(s: String): Boolean {
        val regex = Regex("([+-]?(\\d+(\\.\\d*)?|(\\.\\d+)))([eE][+-]?\\d+)?")
        return regex.matches(s)
    }
}

解法2：模拟

暴力模拟逻辑会比较乱，可以做一个简单的分类，这样相对会比较清晰。

有效数字有三种可能的字符串形式：

1. 整数
2. 小数
3. 科学计数

针对三种形式的数字，分别写一个校验器做判断即可。

在科学计数的校验器中，可以去除科学计数的特征字符，再复用整数校验器和小数校验器的逻辑。

class Solution {
    private val validator = Decorator()

    fun isNumber(s: String): Boolean {
        return validator.validate(s)
    }
}

interface Validator {
    fun validate(s: String): Boolean
}

class IntValidator : Validator {
    override fun validate(s: String): Boolean {
        if (s.isEmpty()) return false
        return s.all { it.isDigit() }
    }
}

class FloatValidator : Validator {
    override fun validate(s: String): Boolean {
        val dotIndex = s.indexOf(".")
        if (dotIndex == -1) return false
        if (s.length == 1) return false
        val intPart = s.substring(0, dotIndex)
        val decimalPart = s.substring(dotIndex + 1, s.length)
        return intPart.all { it.isDigit() } && decimalPart.all { it.isDigit() }
    }
}

class ScienceFormatValidator : Validator {
    private val floatValidator = FloatValidator()
    private val intValidator = IntValidator()

    override fun validate(s: String): Boolean {
        val eIndex = s.indexOf("e")
        if (eIndex == -1) return false
        if (eIndex == s.length - 1) return false

        val left = s.substring(0, eIndex)

        var right = s.substring(eIndex + 1, s.length)
        if (right[0] == '+' || right[0] == '-') {
            right = right.substring(1, right.length)
        }

        return (intValidator.validate(left) || floatValidator.validate(left)) && intValidator.validate(right)
    }
}

class Decorator : Validator {
    private val validators = listOf(
            IntValidator(),
            FloatValidator(),
            ScienceFormatValidator()
    )

    override fun validate(s: String): Boolean {
        val str = s.trimSpaceAndSign()
        validators.forEach { validator ->
            if (validator.validate(str)) {
                return true
            }
        }
        return false
    }
}

fun String.trimSpaceAndSign(): String {
    val s = trim()
    return if (s.isNotEmpty() && (s[0] == '+' || s[0] == '-')) {
        s.substring(1)
    } else s
}

解法3：DFA

字符匹配规则的过程，可以看作是状态转移的过程，字符作为输入，即状态改变的条件，让一个状态产生转移另一个状态，如果能转换到最终状态，说明字符串是匹配的。

可以用状态机来解决字符串匹配。这里使用DFA，即确定有穷状态机，对每个状态和输入符号可以得到下一个唯一到状态。

那么问题就转变为：

1. 有哪些状态？
2. 初始状态是什么？
3. 结束状态是什么？
4. 输入有哪些？
5. 状态转移失败怎么办？
6. 状态转移的所有情况有哪些？

有哪些状态？

我们把所有正确的、互相独立的状态列出来，然后看输入什么字符可以从一个状态转换到另一个状态，就构建出了状态机。

可以把 当前处理到有效数字字符串的哪个部分 当作状态，所有的状态：

0.空字符串
1.符号位
2.整数部分数字
3.左侧有整数的小数点
4.左侧无整数的小数点
5.小数部分的数字
6.指数字符e或E
7.指数后面的符号位
8.指数后面的整数部分

初始状态是什么？

0.空字符串

结束状态是什么？

2.整数部分数字
3.左侧有整数的小数点
5.小数部分的数字
8.指数后面的整数部分

输入有哪些？

• 空格
• 正负号 + 或-
• 数字0-9
• 点 .
• 英文字母e或E
• 其他字符

状态转移失败怎么办？

如果对于某个输入不能转换到下一个状态，应该提前终止匹配。

状态转移的所有情况有哪些？

可以用状态表描述所有状态转移的情况，结合规则和示例定义所有状态的转移情况。

如果状态不可转移，用-1表示。

状态	空格	+/-	0-9	.	e/E	其他
0.空字符串	0	1	2	4	-1	-1
1.符号位	-1	-1	2	4	-1	-1
2.整数部分数字	-1	-1	2	3	6	-1
3.左侧有整数的小数点	-1	-1	5	-1	6	-1
4.左侧无整数的小数点	-1	-1	5	-1	-1	-1
5.小数部分的数字	-1	-1	5	-1	6	-1
6.指数字符e或E	-1	7	8	-1	-1	-1
7.指数后面的符号位	-1	-1	8	-1	-1	-1
8.指数后面的整数部分	-1	-1	8	-1	-1	-1

状态表怎么存储？

• 二维数组。
• 哈希表嵌套，不存储-1的状态，这样还可以节约一点空间。

复杂度

时间复杂度：O(n)

字符串长度为n，需要遍历字符串所有字符。

状态转移查表只需要O(1)时间。

空间复杂度：O(1)

虽然状态表占用一定的空间，但跟字符串长度无关，并且大小固定，所以可以认为是常数空间。

class Solution {
    /**
     *
     *      |       状态        |空格|+/-|0-9|. |e/E|其他|
     *      | -----------------|----|---|---|--|---|--|
     *      |0.空字符串          |0  |1  |2  |4  |-1 |-1|
     *      |1.符号位            |-1 |-1 |2  |4 |-1  |-1|
     *      |2.整数部分数字       |-1 |-1 |2  |3  |6  |-1|
     *      |3.左侧有整数的小数点  |-1 |-1 |5  |-1 |6  |-1|
     *      |4.左侧无整数的小数点  |-1 |-1 |5  |-1 |-1 |-1|
     *      |5.小数部分的数字     |-1 |-1 |5  |-1 |6  |-1|
     *      |6.指数字符e或E       |-1 |7 |8  |-1 |-1 |-1|
     *      |7.指数后面的符号位    |-1 |-1 |8 |-1 |-1 |-1|
     *      |8.指数后面的整数部分  |-1 |-1 |8 |-1 |-1 |-1|
     */
    private val table = arrayOf(
        intArrayOf(0, 1, 2, 4, -1, -1),
        intArrayOf(-1, -1, 2, 4, -1, -1),
        intArrayOf(-1, -1, 2, 3, 6, -1),
        intArrayOf(-1, -1, 5, -1, 6, -1),
        intArrayOf(-1, -1, 5, -1, -1, -1),
        intArrayOf(-1, -1, 5, -1, 6, -1),
        intArrayOf(-1, 7, 8, -1, -1, -1),
        intArrayOf(-1, -1, 8, -1, -1, -1),
        intArrayOf(-1, -1, 8, -1, -1, -1)
    )

    private val finalState = arrayOf(2, 3, 5, 8)

    fun isNumber(s: String): Boolean {
        var state = 0
        for (c in s) {
            state = table[state][c.index]
            if (state == -1) return false
        }
        return state in finalState
    }

    private val Char.index: Int
        get() = when (this) {
            ' ' -> 0
            '+', '-' -> 1
            in '0'..'9' -> 2
            '.' -> 3
            'e', 'E' -> 4
            else -> 5
        }
}