LeetCode-表示数值的字符串(每日一题)

题目描述

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

解法

1. 正则表达式

思路：一开始在剑指Offer上做这道题的时候使用正则表达式进行匹配。返回字符串是否能匹配正则表达式的结果。

^ 匹配字符串开头(在方括号中使用表示‘非’)
$ 匹配字符串结尾
[] 可以有的结果
() 分组
\d 匹配数字
. 匹配任意字符(除了\n)
* 0个或多个
? 0个或一个
+ 一个或多个

import java.util.regex.Pattern;

class Solution {
    public boolean isNumber(String s) {
        String pattern = "^[\\+\\-]?(\\d+(\\.\\d*)?|\\.\\d+)([eE][\\+\\-]?\\d+)?$";
        return Pattern.matches(pattern, s.trim());
    }
}

(\\d+(\\.\\d*)?|\\.\\d+)用来匹配小数点前需要有数字以及小数点后需要有数字的情况，即匹配3.或者.1而防止仅有一个.的情况出现。

2. 确定有限状态自动机

确定优先状态自动机是一种计算模型。它包含一系列状态，这些状态中：

有一个特殊状态，称为初始状态
还有一系列状态称为接受状态

起初，这个自动机处于初始状态。随后，按顺序读取每一个字符，根据当前状态和读取的字符，按照转移规则决定是否转移到下一个状态。整个字符串全部读完，此时自动机处于某个接收状态，判断字符串被接受，否则被拒绝。

转移过程中如果违反了转移规则，那么也判断字符串被拒绝。

它正是实现正则表达式的基础。

我们可以通过设置一系列标记来规定如何转移。

class Solution {
    public boolean isNumber(String s) {
        // null或者空字符串返回false
        if (s == null || s.length() == 0) return false;
        // 设置标记
        boolean isNum = false, isDot = false, iseOrE = false;
        // 去除首尾空格
        String str = s.trim();
        // 遍历字符串
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                // 遇到数字，将isNum置为true
                isNum = true;
            } else if (str.charAt(i) == '.') {
                // 遇到小数点，如果之前有小数点或者e，返回false
                if (isDot || iseOrE) return false;
                isDot = true;
            } else if (str.charAt(i) == 'e' || str.charAt(i) == 'E') {
                // 遇到e，如果之前有e或者没有数字，返回false
                if (iseOrE || !isNum) return false;
                iseOrE = true;
                // e后面也需要跟上数字，防止3e这种情况出现，将isNum置为false
                isNum = false;
            } else if (str.charAt(i) == '-' || str.charAt(i) == '+') {
                // +-只能出现在第一位以及e后面一位
                if (i == 0 || str.charAt(i - 1) == 'e' || str.charAt(i - 1) == 'E') continue;
                return false;
            } else {
                // 其它情况直接终止转移
                return false;
            }
        }
        // 返回isNum的结果
        return isNum;
    }
}