有效数字

Problem: 65.有效数字

构造DFA状态转换表

写出正规式。


d = 0|1|2|3|4|5|6|7|8|9
(-|+|)(dd*(.d*|)|d*.dd*)((e|E)(-|+|)dd*|)

根据正规式画出 NFA。

NFA 确定化（NFA $\rightarrow$ DFA）。

ㅤ	-	+	d	.	e	E
`{0,1,5}`Sº	`{1,5}`	`{1,5}`	`{2,3,5,8,12}`	`{6}`	ㅤ	ㅤ
`{1,5}`A	ㅤ	ㅤ	`{2,3,5,8,12}`	`{6}`	ㅤ	ㅤ
`{2,3,5,8,12}`B*	ㅤ	ㅤ	`{2,3,5,8,12}`	`{4,6,8,12}`	`{9,10}`	`{9,10}`
`{6}`C	ㅤ	ㅤ	`{7,8,12}`	ㅤ	ㅤ	ㅤ
`{4,6,8,12}`D*	ㅤ	ㅤ	`{4,7,8,12}`	ㅤ	`{9,10}`	`{9,10}`
`{9,10}`E	`{10}`	`{10}`	`{11,12}`	ㅤ	ㅤ	ㅤ
`{7,8,12}`F*	ㅤ	ㅤ	`{7,8,12}`	ㅤ	`{9,10}`	`{9,10}`
`{4,7,8,12}`G*	ㅤ	ㅤ	`{4,7,8,12}`	ㅤ	`{9,10}`	`{9,10}`
`{10}`H	ㅤ	ㅤ	`{11,12}`	ㅤ	ㅤ	ㅤ
`{11,12}`I*	ㅤ	ㅤ	`{11,12}`	ㅤ	ㅤ	ㅤ

DFA 最小化（已无法最小化）。

表驱动法具体实现

写出 DFA 状态转换表。

ㅤ	'-'	'+'	'0'-'9'	'.'	'e'	'E'
Sº	A	A	B*	C	ㅤ	ㅤ
A	ㅤ	ㅤ	B*	C	ㅤ	ㅤ
B*	ㅤ	ㅤ	B*	D*	E	E
C	ㅤ	ㅤ	F*	ㅤ	ㅤ	ㅤ
D*	ㅤ	ㅤ	G*	ㅤ	E	E
E	H	H	I*	ㅤ	ㅤ	ㅤ
F*	ㅤ	ㅤ	F*	ㅤ	E	E
G*	ㅤ	ㅤ	G*	ㅤ	E	E
H	ㅤ	ㅤ	I*	ㅤ	ㅤ	ㅤ
I*	ㅤ	ㅤ	I*	ㅤ	ㅤ	ㅤ

各状态对于 -/+ 和 e/E 的转换动作一致，为了节省数组空间，对该表进一步简化。

ㅤ	'-'/'+'	'0'-'9'	'.'	'e'/'E'
Sº	A	B*	C	ㅤ
A	ㅤ	B*	C	ㅤ
B*	ㅤ	B*	D*	E
C	ㅤ	F*	ㅤ	ㅤ
D*	ㅤ	G*	ㅤ	E
E	H	I*	ㅤ	ㅤ
F*	ㅤ	F*	ㅤ	E
G*	ㅤ	G*	ㅤ	E
H	ㅤ	I*	ㅤ	ㅤ
I*	ㅤ	I*	ㅤ	ㅤ

代码

Java


class Solution {
    public boolean isNumber(String s) {
        int[][] dfaTable = new int[][] {
            {1, 2, 3, -1},
            {-1, 2, 3, -1},
            {-1, 2, 4, 5},
            {-1, 6, -1, -1},
            {-1, 7, -1, 5},
            {8, 9, -1, -1},
            {-1, 6, -1, 5},
            {-1, 7, -1, 5},
            {-1, 9, -1, -1},
            {-1, 9, -1, -1}
        };
        int[] endOfStates = new int[] {
            2, 4, 6, 7, 9
        };
        int state = 0;
        for (int i = 0; i < s.length() && state != -1; i++) {
            int charIndex = getCharIndex(s.charAt(i));
            if (charIndex == -1) {
                return false;
            }
            state = dfaTable[state][charIndex];
        }
        for (int i = 0; i < endOfStates.length; i++) {
            if (state == endOfStates[i]) {
                return true;
            }
        }
        return false;
    }
    int getCharIndex(char c) {
        if (c == '-' || c == '+') {
            return 0;
        } else if (c >= '0' && c <= '9') {
            return 1;
        } else if (c == '.') {
            return 2;
        } else if (c == 'e' || c == 'E') {
            return 3;
        } else {
            return -1;
        }
    }
}

Python3


class Solution:
    def isNumber(self, s: str):
        dfaTable = [
            [1, 2, 3, -1],
            [-1, 2, 3, -1],
            [-1, 2, 4, 5],
            [-1, 6, -1, -1],
            [-1, 7, -1, 5],
            [8, 9, -1, -1],
            [-1, 6, -1, 5],
            [-1, 7, -1, 5],
            [-1, 9, -1, -1],
            [-1, 9, -1, -1]
        ]
        endOfStates = [
            2, 4, 6, 7, 9
        ]

        state = 0
        for c in s:
            charIndex = self.getCharIndex(c)
            if charIndex == -1:
                return False
            state = dfaTable[state][charIndex]
            if state == -1:
                break

        for endOfState in endOfStates:
            if state == endOfState:
                return True
        return False

    def getCharIndex(self, c: str):
        if c == '-' or c == '+':
            return 0
        elif c >= '0' and c <= '9':
            return 1
        elif c == '.':
            return 2
        elif c == 'e' or c == 'E':
            return 3
        else:
            return -1

TypeScript


var isNumber = (s: string) => {
    const dfaTable = [
        [1, 2, 3, -1],
        [-1, 2, 3, -1],
        [-1, 2, 4, 5],
        [-1, 6, -1, -1],
        [-1, 7, -1, 5],
        [8, 9, -1, -1],
        [-1, 6, -1, 5],
        [-1, 7, -1, 5],
        [-1, 9, -1, -1],
        [-1, 9, -1, -1]
    ];
    const endOfStates = [
        2, 4, 6, 7, 9
    ];
    let state = 0;
    for (let i = 0; i < s.length && state != -1; i++) {
        const charIndex = getCharIndex(s.charAt(i));
        if (charIndex == -1) {
            return false;
        }
        state = dfaTable[state][charIndex];
    }
    for (let i = 0; i < endOfStates.length; i++) {
        if (state == endOfStates[i]) {
            return true;
        }
    }
    return false;
}
var getCharIndex = (c: string) => {
    if (c == '-' || c == '+') {
        return 0;
    } else if (c >= '0' && c <= '9') {
        return 1;
    } else if (c == '.') {
        return 2;
    } else if (c == 'e' || c == 'E') {
        return 3;
    } else {
        return -1;
    }
}

JavaScript


var isNumber = (s) => {
    const dfaTable = [
        [1, 2, 3, -1],
        [-1, 2, 3, -1],
        [-1, 2, 4, 5],
        [-1, 6, -1, -1],
        [-1, 7, -1, 5],
        [8, 9, -1, -1],
        [-1, 6, -1, 5],
        [-1, 7, -1, 5],
        [-1, 9, -1, -1],
        [-1, 9, -1, -1]
    ];
    const endOfStates = [
        2, 4, 6, 7, 9
    ];
    let state = 0;
    for (let i = 0; i < s.length && state != -1; i++) {
        const charIndex = getCharIndex(s.charAt(i));
        if (charIndex == -1) {
            return false;
        }
        state = dfaTable[state][charIndex];
    }
    for (let i = 0; i < endOfStates.length; i++) {
        if (state == endOfStates[i]) {
            return true;
        }
    }
    return false;
}
var getCharIndex = (c) => {
    if (c == '-' || c == '+') {
        return 0;
    } else if (c >= '0' && c <= '9') {
        return 1;
    } else if (c == '.') {
        return 2;
    } else if (c == 'e' || c == 'E') {
        return 3;
    } else {
        return -1;
    }
}


public class Solution {
    public bool IsNumber(String s) {
        int[][] dfaTable = new int[][] {
            new int[] {1, 2, 3, -1},
            new int[] {-1, 2, 3, -1},
            new int[] {-1, 2, 4, 5},
            new int[] {-1, 6, -1, -1},
            new int[] {-1, 7, -1, 5},
            new int[] {8, 9, -1, -1},
            new int[] {-1, 6, -1, 5},
            new int[] {-1, 7, -1, 5},
            new int[] {-1, 9, -1, -1},
            new int[] {-1, 9, -1, -1}
        };
        int[] endOfStates = new int[] {
            2, 4, 6, 7, 9
        };
        int state = 0;
        for (int i = 0; i < s.Length && state != -1; i++) {
            int charIndex = GetCharIndex(s[i]);
            if (charIndex == -1) {
                return false;
            }
            state = dfaTable[state][charIndex];
        }
        for (int i = 0; i < endOfStates.Length; i++) {
            if (state == endOfStates[i]) {
                return true;
            }
        }
        return false;
    }
    int GetCharIndex(char c) {
        if (c == '-' || c == '+') {
            return 0;
        } else if (c >= '0' && c <= '9') {
            return 1;
        } else if (c == '.') {
            return 2;
        } else if (c == 'e' || c == 'E') {
            return 3;
        } else {
            return -1;
        }
    }
}


int getCharIndex(char c) {
    if (c == '-' || c == '+') {
        return 0;
    } else if (c >= '0' && c <= '9') {
        return 1;
    } else if (c == '.') {
        return 2;
    } else if (c == 'e' || c == 'E') {
        return 3;
    } else {
        return -1;
    }
}
bool isNumber(char* s) {
    int dfaTable[10][4] = {
        {1, 2, 3, -1},
        {-1, 2, 3, -1},
        {-1, 2, 4, 5},
        {-1, 6, -1, -1},
        {-1, 7, -1, 5},
        {8, 9, -1, -1},
        {-1, 6, -1, 5},
        {-1, 7, -1, 5},
        {-1, 9, -1, -1},
        {-1, 9, -1, -1}
    };
    int endOfStates[5] = {
        2, 4, 6, 7, 9
    };
    int state = 0;
    for (int i = 0; i < strlen(s) && state != -1; i++) {
        int charIndex = getCharIndex(*(s + i));
        if (charIndex == -1) {
            return false;
        }
        state = dfaTable[state][charIndex];
    }
    for (int i = 0; i < sizeof(endOfStates) / sizeof(int); i++) {
        if (state == endOfStates[i]) {
            return true;
        }
    }
    return false;
}

复杂度分析

时间复杂度： $O(n)$ ， $n=s.length$ 。

空间复杂度： $O(n)$ ， $n=s.length$ 。