题目
有效数字(按顺序)可以分成以下几个部分:
- 一个 小数 或者 整数
- (可选)一个 ‘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、正则表达式的思路很明显,不细说。可以参考解法
2、状态机其实是比较有意思且规范的一个解法,具体思路可以直接参考官方解法。其实难点就在于完整梳理整个过程中的所有状态,保证不重不漏。然后根据状态机进行编程和状态转移,如果在状态转移过程中出现无效转移、或者最后的状态不是一种结束状态,那么就认为输入条件是不符合状态机规范的。
3、至于分类讨论,其实就是直接分析有效数字存在的规律,然后直接进行拆解。可以参考此解法,先按e进行拆分,然后左右两侧分别判断是否是有效数字。这里边还需要考虑e和小数点只能出现一次,所以该解法还是需要考虑比较多的细节,不过实现代码写的很精简。
复杂度
时间复杂度很明显是O(n), 空间复杂度是O(1)
代码就不贴了,上面链接都有详细代码。
总结
这种用有限状态自动机(DFA)实现的题目之前没见过,很有意思,记录一下。
另外,看到资料说:正则表达式的实现基础也是DFA,可以扩展了解一下。