状态机_剑指offer.20_表示数值的字符串

🌸题目

🍁请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”、”5e2”、”-123”、”3.1416”、”-1E-16”、”0123”都表示数值，但”12e”、”1a3.14”、”1.2.3”、”+-5”及”12e+5.4”都不是。

🌸方法一：暴力模拟

目的是判断m在哪个排序数组中。在numbers [m]>numbers[i] 情况下,

public boolean isNumber(String s) {
	if(s.length() <= 0 || s == null) {
		return false;
	}
	
	boolean isEExist = false;// 记录 e 和 E 是否存在
	boolean isDotExist = false;// 记录 小数点 是否存在
	boolean numberic = false;// 记录 当前数字 是否合法
	char[] chars = s.trim().toCharArray();
	
	for(int i = 0; i < chars.length; i++) {
		char c = chars[i];
		if(c >= '0' && c <= '9') {
			numberic = true;
		}else if(c == '+' || c == '-') {
			//+-出现在0位置或者e/E的后面第一个位置才是合法的
			if(i != 0 && chars[i - 1] != 'e' && chars[i - 1] != 'E') {
				return false;
			}
		}else if(c == '.') {
			 //.之前不能出现.或者e
			if(isEExist || isDotExist) {
				return false;
			}
			isDotExist = true;
		}else if(c == 'E' || c == 'e') {// E/e之前必须有数，且没出现过
			 //e之前不能出现e，必须出现数
			if(isEExist || !numberic) {
				return false;
			}
			isEExist = true;
			numberic = false;//重置numberic，排除123e或者123e+的情况,确保e之后也出现数
		}else {//其他不合法字符
			return false;
		}
	}
	return numberic;
}

🌸方法二：有限状态自动机

🍁分析

本题使用有限状态自动机。根据字符类型和合法数值的特点，先定义状态，再画出状态转移图，最后编写代码即可。

字符类型：

空格「」、数字「 0—90—9 」、正负号「 +-+− 」、小数点「 .. 」、幂符号「 eEeE 」。

状态定义：

按照字符串从左到右的顺序，定义以下 9 种状态。

0 开始的空格
1 幂符号前的正负号
2小数点前的数字
3小数点、小数点后的数字
4当小数点前为空格时，小数点、小数点后的数字
5幂符号
6幂符号后的正负号
7幂符号后的数字
8结尾的空格

结束状态：

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

🍁算法流程：

初始化：

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

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

复杂度分析：

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

class Solution {
    public boolean isNumber(String s) {
        Map[] states = {
            new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
            new HashMap<>() {{ put('d', 2); put('.', 4); }},                           // 1.
            new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
            new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }},              // 3.
            new HashMap<>() {{ put('d', 3); }},                                        // 4.
            new HashMap<>() {{ put('s', 6); put('d', 7); }},                           // 5.
            new HashMap<>() {{ put('d', 7); }},                                        // 6.
            new HashMap<>() {{ put('d', 7); put(' ', 8); }},                           // 7.
            new HashMap<>() {{ put(' ', 8); }}                                         // 8.
        };
        int p = 0;
        char t;
        for(char c : s.toCharArray()) {
            if(c >= '0' && c <= '9') t = 'd';
            else if(c == '+' || c == '-') t = 's';
            else if(c == 'e' || c == 'E') t = 'e';
            else if(c == '.' || c == ' ') t = c;
            else t = '?';
            if(!states[p].containsKey(t)) return false;
            p = (int)states[p].get(t);
        }
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
}

class Solution:
    def isNumber(self, s: str) -> bool:
        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 s:
            if '0' <= c <= '9': t = 'd' # digit
            elif c in "+-": t = 's'     # sign
            elif c in "eE": t = 'e'     # e or 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)