題⽬描述

請實現⼀個函數⽤來判斷字符串str是否表示數值（包括科學計數法的數字，⼩數和整數）。科學計數法的數字(按順序）可以分成以下⼏個部分:

1. 若⼲空格
2. ⼀個整數或者⼩數
3. （可選）⼀個 ' e ' 或 ' E ' ，後⾯跟着⼀個整數(可正可負)
4. 若⼲空格

⼩數（按順序）可以分成以下⼏個部分：

1. 若⼲空格
2. （可選）⼀個符號字符（'+' 或 '-'）
3. 可能是以下描述格式之⼀:
   1. ⾄少⼀位數字，後⾯跟着⼀個點 '.'
   2. ⾄少⼀位數字，後⾯跟着⼀個點 '.' ，後⾯再跟着⾄少⼀位數字
   3. ⼀個點 '.' ，後⾯跟着⾄少⼀位數字
4. 若⼲空格

整數（按順序）可以分成以下⼏個部分：

1. 若⼲空格
2. （可選）⼀個符號字符（' + ' 或 ' - ')
3. ⾄少⼀位數字
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），加號 '+' ，減號 '-' ，空格 ' ' 或者點 '.' 。
3. 如果懷疑⽤例是不是能表示為數值的，可以使⽤python 的print(float(str)) 去查看

示例1
輸⼊："123.45e+6"
返回值：true

示例2
輸⼊："1.2.3"
返回值：false

思路及解答

暴力分析拆解

主要是分析好判斷分⽀，可以定義⼏個變量：

• hashNum : 是否已經有數字
• hashE ：是否已經有E
• hasSign ：是否已經有符號
• hasDot ：是否已經有⼩數點

⾸先，初始化當前的索引index =0 ，字符串頭部的空格需要跳過。

• 循環判斷索引是否在有效的範圍內：
  • 循環判斷是否是數字，是數字則更新hasNum = true ,並且索引後移，直到不是數字的時候，跳出循環。
• 跳出循環後，需要判斷當前的index 是否合法，不合法直接break
• 取出當前索引的字符c ：
  • 如果c 是e 或者E ：
    • 如果前⾯已經出現過E ，或者前⾯沒有數字，直接返回false
    • 否則， hasE 置為true ，其他的置為false ，也就是E後⾯可以繼續出現符號數字和⼩數點了
  • 如果c 是“ + ”或者“ - ”：
    • 前⾯如果已經出現過數字或者符號或者⼩數點，都不是合法的
    • 否則hasSign 置為true ，表示符號出現過
  • 如果c 是⼩數點“ . ”
    • 如果前⾯已經有⼩數點或者有E出現了，那麼就是⾮法的，返回false
    • 否則hasDot 置為true
  • 如果c 為空格，直接跳出循環
  • 否則，直接返回false
• 最後也需要跳過空格
• 最後判斷是否合法的條件是：是否到達最後⼀個字符，並且出現過數字

public boolean isNumeric(String str) {
	int size = str.length();
	int index= 0 ;
	// 默認全部是false
	boolean hashNum=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++;
			// 表示前⾯有數字
			hashNum = true;
		}
- 
		// 到末尾直接跳出
		if(index==size){
			break;
		}
- 
		char c = str.charAt(index);
		if(c=='e'||c=='E'){
			// 前⾯有E或者沒有數字在前⾯
			if(hasE||!hashNum){
				return false;
			}
			hasE = true;
			// 出現E了後⾯⼜可以出現數字了
			hashNum = false;
			hasSign = false;
			hasDot = false;
		}else if(c=='+'||c=='-'){
			if(hasSign||hashNum||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<size&&str.charAt(index)==' '){
		index++;
	}
	return hashNum &&index==size;
}

這道題，其實本質是狀態的切換，最最重要的⼀點，是 E 出現之後，其實⼩數點和符號，和數字，都是可以再出現的，可以理解為 E 就是⼀個分割線。

正則表達式

直接藉助正則表達式進⾏匹配，但是並不太推薦這種解法：

public class Solution {

	public boolean isNumeric (String str) {
		// 核心正則表達式：處理空格、符號、小數、指數部分
		
		// ^表示開頭 $ 表示結尾 java中兩個\\ 代表⼀個\
		// \\s*開頭可能有空格
		// * 零次或多次匹配前⾯的字符或⼦表達式
		// ？零次或⼀次匹配前⾯的字符或⼦表達式
		// + ⼀次或多次匹配前⾯的字符或⼦表達式
		// [] 字符集。匹配包含的任⼀字符
		// (:? )匹配 pattern 但不捕獲該匹配的⼦表達式，即它是⼀個⾮捕獲匹配
		String p = "^\\s*[+-]?(\\d*\\.\\d+|\\d+(\\.\\d*)?)(?:[eE][+-]?\\d+)?$";
		return Pattern.matches(p,str);
	}
}

• O(n)時間複雜度
• O(1)空間複雜度

有限狀態機

使用確定有限狀態機(DFA)來精確建模數值的判斷過程。

有限狀態機法：通過狀態轉移精確控制數值格式。定義9種狀態，根據輸入字符進行狀態轉移

public boolean isNumberDFA(String str) {
    if (str == null) return false;
    
    // 狀態定義：0-8共9種狀態
    // 0: 起始空格 1: 符號 2: 整數數字 3: 小數點前無數字 
    // 4: 小數點後有數字 5: 指數e 6: 指數符號 7: 指數數字 8: 結尾空格
    int state = 0; // 初始狀態
    
    // 狀態轉移表
    int[][] transitionTable = {
        // 空格 符號 數字 小數點 e/E 其他
        {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)