leetcode:65. 有效数字

我不是女神ヾ 2022-04-08 11:48 183阅读 0赞

## 题目: ##

验证给定的字符串是否为数字。

例如:  
“0” => true  
" 0.1 " => true  
“abc” => false  
“1 a” => false  
“2e10” => true

说明: 我们有意将问题陈述地比较模糊。在实现代码之前，你应当事先思考所有可能的情况。

## 分析: ##

使用DFA算法，首先先判断遍历过程中可能含有的所有状态，标记如下：  
\[\]表示可能存在  
![在这里插入图片描述][20181213175610283.png]

## 代码: ##

public boolean isNumber(String s) {
    
    		s = s.trim();
    		char[] c = s.toCharArray();
    		int[][] FSM = { 
    				{ -1,  0,  1, -1, 2 }, 
    				{ -1, -1, -1, -1, 3 }, 
    				{ -1, -1,  4,  5, 2 }, 
    				{ -1, -1, -1,  5, 3 },
    				{ -1, -1, -1,  5, 4 }, 
    				{ -1,  5, -1, -1, 6 }, 
    				{ -1, -1, -1, -1, 6 } };
    
    		int now = 0;
    		for (int i = 0; i < c.length; i++) {
    			switch (c[i]) {
    			case '-':
    				now = FSM[now][1];
    				break;
    			case '+':
    				now = FSM[now][1];
    				break;
    			case '.':
    				now = FSM[now][2];
    				break;
    			case 'e':
    				now = FSM[now][3];
    				break;
    			case 'E':
    				now = FSM[now][3];
    				break;
    			default: {
    				if (c[i] >= '0' && c[i] <= '9')
    					now = FSM[now][4];
    				else
    					now = FSM[now][0];
    			}
    			}
    			if (now == -1)
    				return false;
    		}
    		return now == 2 || now == 3 || now == 4 || now == 6;
    	}

## 效率: ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70]

## 总结: ##

有限状态机的思路简单,代码简单,推导状态转换矩阵较为复杂

[20181213175610283.png]: /images/20220405/d905f53839604a92a51de35b45b204bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70]: /images/20220405/51ca6891ee6d4a02abb6d08ee60a900c.png