📃 题目描述

题目链接：剑指 Offer 20. 表示数值的字符串 (opens new window)

🔔 解题思路

确定有限状态自动机 - Deterministic Finite Automaton，DFA（以下简称「自动机」）是一类计算模型。它包含一系列状态，这些状态中：

• 有一种特殊的状态，被称作「初始状态」。
• 还有一系列状态被称为「接受状态」，它们组成了一个特殊的集合。其中，一个状态可能既是「初始状态」，也是「接受状态」。

起初，这个自动机处于「初始状态」。随后，它顺序地读取字符串中的每一个字符，并根据当前状态和读入的字符，按照某个事先约定好的「转移规则」，从当前状态转移到下一个状态；当状态转移完成后，它就读取下一个字符。当字符串全部读取完毕后，如果自动机处于某个「接受状态」，则判定该字符串「被接受」；否则，判定该字符串「被拒绝」。

注意：如果输入的过程中某一步转移失败了，即不存在对应的「转移规则」，此时计算将提前中止。在这种情况下我们也判定该字符串「被拒绝」。

一个自动机，总能够回答某种形式的「对于给定的输入字符串 S，判断其是否满足条件 P」的问题。在本题中，条件 P 即为「构成合法的表示数值的字符串」。

自动机驱动的编程，可以被看做一种暴力枚举方法的延伸：它穷尽了在任何一种情况下，对应任何的输入，需要做的事情。

自动机在计算机科学领域有着广泛的应用。在算法领域，它与大名鼎鼎的字符串查找算法「KMP」算法有着密切的关联；在工程领域，它是实现「正则表达式」的基础。

※　DFA 即 Deterministic Finite Automaton，确定有限自动机

状态 id	状态描述	可转移到的状态
0	开始空格	0,1,2,4
1	e/E 之前的 +/-（符号位）	2,4
2	. 之前的数字（整数部分）	2,3,6,9
3	左边有数字的 .	5,6,9
4	右边有数字的 .	5
5	. 之后的数字（小数部分）	5,6,9
6	e/E	7,8
7	e/E 之后的 +/-（指数部分的符号位）	8
8	e/E 之后的数字（指数部分的整数部分）	8,9
9	结尾空格	9

class Solution {
    public boolean isNumber(String s) {
        // 构造状态机，key:当前状态 value:<当前字符类型, 转移到的状态>
        Map<State, Map<CharType, State>> transfer = new HashMap<>();

        // STATE_INITIAL 可转移的状态
        Map<CharType, State> initialMap = new HashMap<>() {{
            put(CharType.CHAR_SPACE, State.STATE_INITIAL);
            put(CharType.CHAR_SIGN, State.STATE_INT_SIGN);
            put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
            put(CharType.CHAR_POINT, State.STATE_POINT_RIGHT);
        }};
        transfer.put(State.STATE_INITIAL, initialMap);

        Map<CharType, State> intSignMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
            put(CharType.CHAR_POINT, State.STATE_POINT_RIGHT);
        }};
        transfer.put(State.STATE_INT_SIGN, intSignMap);

        Map<CharType, State> integerMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
            put(CharType.CHAR_EXP, State.STATE_EXP);
            put(CharType.CHAR_POINT, State.STATE_POINT_LEFT);
            put(CharType.CHAR_SPACE, State.STATE_END);
        }};
        transfer.put(State.STATE_INTEGER, integerMap);

        Map<CharType, State> pointMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
            put(CharType.CHAR_EXP, State.STATE_EXP);
            put(CharType.CHAR_SPACE, State.STATE_END);
        }};
        transfer.put(State.STATE_POINT_LEFT, pointMap);

        Map<CharType, State> pointWithoutIntMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
        }};
        transfer.put(State.STATE_POINT_RIGHT, pointWithoutIntMap);

        Map<CharType, State> fractionMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
            put(CharType.CHAR_EXP, State.STATE_EXP);
            put(CharType.CHAR_SPACE, State.STATE_END);
        }};
        transfer.put(State.STATE_FRACTION, fractionMap);

        Map<CharType, State> expMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_EXP_INTEGER);
            put(CharType.CHAR_SIGN, State.STATE_EXP_SIGN);
        }};
        transfer.put(State.STATE_EXP, expMap);

        Map<CharType, State> expSignMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_EXP_INTEGER);
        }};
        transfer.put(State.STATE_EXP_SIGN, expSignMap);

        Map<CharType, State> expNumberMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_EXP_INTEGER);
            put(CharType.CHAR_SPACE, State.STATE_END);
        }};
        transfer.put(State.STATE_EXP_INTEGER, expNumberMap);

        Map<CharType, State> endMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_SPACE, State.STATE_END);
        }};
        transfer.put(State.STATE_END, endMap);

        // 根据状态机遍历 s 做状态转移
        int len = s.length();
        State curState = State.STATE_INITIAL;

        for (char c : s.toCharArray()) {
            CharType charType = getCharType(c);
            // 无法根据 type 转移到下一个状态 
            if (!transfer.get(curState).containsKey(charType)) {
                return false;
            }

            curState = transfer.get(curState).get(charType);
        }
        
        return curState == State.STATE_INTEGER || 
               curState == State.STATE_POINT_LEFT || 
               curState == State.STATE_FRACTION || 
               curState == State.STATE_EXP_INTEGER || 
               curState == State.STATE_END;
    }

    // 状态
    public enum State {
        STATE_INITIAL(0),
        STATE_INT_SIGN(1),
        STATE_INTEGER(2),
        STATE_POINT_LEFT(3),
        STATE_POINT_RIGHT(4),
        STATE_FRACTION(5),
        STATE_EXP(6),
        STATE_EXP_SIGN(7),
        STATE_EXP_INTEGER(8),
        STATE_END(9);

        private final int value;

        State (int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }
    }

    // 字符类型
    public enum CharType {
        CHAR_NUMBER,
        CHAR_EXP,
        CHAR_POINT,
        CHAR_SIGN,
        CHAR_SPACE,
        CHAR_ILLEGAL;
    }

    private CharType getCharType(char ch) {
        if (Character.isDigit(ch)) {
            return CharType.CHAR_NUMBER;
        }
        else if (ch == 'e' || ch == 'E') {
            return CharType.CHAR_EXP;
        }
        else if (ch == '.') {
            return CharType.CHAR_POINT;
        }
        else if (ch == '+' || ch == '-') {
            return CharType.CHAR_SIGN;
        }
        else if (ch == ' ') {
            return CharType.CHAR_SPACE;
        }
        
        return CharType.CHAR_ILLEGAL;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：