题解 | #表示数值的字符串#

表示数值的字符串

http://www.nowcoder.com/practice/e69148f8528c4039ad89bb2546fd4ff8

算法思想一：有限状态自动机

解题思路：

根据字符类型和合法数值的特点，先定义状态

字符类型：
空格「」、数字「 0—9 」、正负号「 +- 」、小数点「 .」、幂符号「 eE 」
状态定义：
按照字符串从左到右的顺序，定义以下 9 种状态。
1.开始的空格
2.幂符号前的正负号
3.小数点前的数字
4.小数点、小数点后的数字
5.当小数点前为空格时，小数点、小数点后的数字
6.幂符号
7.幂符号后的正负号
8.幂符号后的数字
9.结尾的空格

合法的结束状态有 2, 3, 7, 8

算法流程：

1、初始化：
1.1、状态转移表 states ：设 states[i] ，其中 i为所处状态， states[i]使用哈希表存储可转移至的状态。键值对 (key, value)含义：若输入 key ，则可从状态 i 转移至状态value 。
1.2、当前状态 p ：起始状态初始化为 p = 0

2、状态转移循环：遍历字符串 str 的每个字符 c 。
2.1、记录字符类型 t ：分为四种情况。
当 c为正负号时，执行 t = 's' ;
当 c 为数字时，执行 t = 'd' ;
当 c 为 e , E 时，执行 t = 'e' ;
当 c 为 . , 空格时，执行 t = c （即用字符本身表示字符类型）;
否则，执行 t = '?' ，代表为不属于判断范围的非法字符，后续直接返回 false 。
2.2、终止条件：若字符类型 t 不在哈希表 states[p]中，说明无法转移至下一状态，因此直接返回 False 。
2.3、状态转移：状态 p 转移至states[p][t] 。
3、返回值：跳出循环后，若状态 p∈2,3,7,8 ，说明结尾合法，返回 True ，否则返回 False 。

代码展示:

Python版本

class Solution:
    def isNumeric(self , str ):
        # write code here
        states = [
            { ' ': 0, 's': 1, 'd': 2, '.': 4 }, # 0. start with 'blank'
            { 'd': 2, '.': 4 } ,                # 1. 'sign' before 'e'
            { 'd': 2, '.': 3, 'e': 5, ' ': 8 }, # 2. 'digit' before 'dot'
            { 'd': 3, 'e': 5, ' ': 8 },         # 3. 'digit' after 'dot'
            { 'd': 3 },                         # 4. 'digit' after 'dot' (‘blank’ before 'dot')
            { 's': 6, 'd': 7 },                 # 5. 'e'
            { 'd': 7 },                         # 6. 'sign' after 'e'
            { 'd': 7, ' ': 8 },                 # 7. 'digit' after 'e'
            { ' ': 8 }                          # 8. end with 'blank'
        ]
        p = 0                           # start with state 0
        for c in str:
            if '0' <= c <= '9': t = 'd' # digit elif c in "+-": t = 's' # sign elif c in "eE": t = 'e' # e&nbs***bsp;E elif c in ". ": t = c # dot, blank else: t = '?' # unknown if t not in states[p]: return False p = states[p][t] return p in (2, 3, 7, 8)

复杂度分析：

时间复杂度 O(N) ：其中 N 为字符串 str 的长度，判断需遍历字符串，每轮状态转移的使用O(1) 时间。
空间复杂度 O(1) ： states 和 p 使用常数大小的额外空间。

算法思想二：常规解法

解题思路：

1、首先定义了四个flag，对应四种字符
是否有数字：hasNum
是否有e：hasE
是否有正负符号：hasSign
是否有点：hasDot
2、其余还定义了字符串长度n以及字符串索引index
3、先处理一下开头的空格，index相应的后移
4、然后进入循环，遍历字符串
如果当前字符c是数字：将hasNum置为true，index往后移动一直到非数字或遍历到末尾位置；如果已遍历到末尾(index == n)，结束循环
如果当前字符c是'e'或'E'：如果e已经出现或者当前e之前没有出现过数字，返回fasle；否则令hasE = true，并且将其他3个flag全部置为false，因为要开始遍历e后面的新数字了
如果当前字符c是+或-：如果已经出现过+或-或者已经出现过数字或者已经出现过'.'，返回flase；否则令hasSign = true
如果当前字符c是'.'：如果已经出现过'.'或者已经出现过'e'或'E'，返回false；否则令hasDot = true
如果当前字符c是' '：结束循环，因为可能是末尾的空格了，但也有可能是字符串中间的空格，在循环外继续处理
如果当前字符c是除了上面5种情况以外的其他字符，直接返回false
5、处理空格，index相应的后移
6、如果当前索引index与字符串长度相等，说明遍历到了末尾，但是还要满足hasNum为true才可以最终返回true，因为如果字符串里全是符号没有数字的话是不行的，而且e后面没有数字也是不行的，但是没有符号是可以的，所以4个flag里只要判断一下hasNum就行；所以最后返回的是hasNum && index == n
7、如果字符串中间有空格，按以上思路是无法遍历到末尾的，index不会与n相等，返回的就是false

代码展示：

JAVA版本

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return bool布尔型
     */
    public boolean isNumeric (String str) {
        int n = str.length();
        int index = 0;
        boolean hasNum = false, hasE = false;
        boolean hasSign = false, hasDot = false;
        while(index < n && str.charAt(index) == ' ') index++; while(index < n){ while(index < n && str.charAt(index) >= '0' && str.charAt(index) <= '9'){ index++; hasNum = true; } if(index == n){ break; } char c = str.charAt(index); if(c == 'e' || c == 'E'){ if(hasE || !hasNum){ return false; } hasE = true; hasNum = false; hasSign = false; hasDot = false; }else if(c == '+' || c == '-'){ if(hasSign || hasNum || hasDot){ return false; } hasSign = true; }else if(c == '.'){ if(hasDot || hasE){ return false; } hasDot = true; }else if(c == ' '){ break; }else{ return false; } index++; } while(index < n && str.charAt(index) == ' ') index++; return hasNum && index == n; } }

复杂度分析：

时间复杂度 O(N) ：其中 N 为字符串 str 的长度，判断需遍历字符串。
空间复杂度 O(1) ：使用常数大小的额外空间。

算法思想三：正则表达式

解题思路：

使用JAVA自带的正则表达式左字符匹配

代码展示：

Java版本

import java.util.*;
import java.util.regex.Pattern;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return bool布尔型
     */
    public boolean isNumeric (String str) {
        // write code here
        //        ^表示开头 $ 表示结尾  java中两个\\ 代表一个\
        //        * 零次或多次匹配前面的字符或子表达式
        //        ？零次或一次匹配前面的字符或子表达式
        //        + 一次或多次匹配前面的字符或子表达式
        //        [] 字符集。匹配包含的任一字符
        //        (:? )匹配 pattern 但不捕获该匹配的子表达式，即它是一个非捕获匹配
        String p = "^[+-]?(\\d*\\.\\d+|\\d+(\\.\\d*)?)(?:[eE][+-]?\\d+)?$";
        return Pattern.matches(p,str);
    }
}