Raccoon丛熊’s Blog
Raccoon丛熊’s Blog
LeetCode
有效数字
有效数字

有效数字

Date
Jun 11, 2023
Created
Oct 15, 2023 05:52 PM
Tags
LeetCode
Algorithm
Java
Python
TypeScript
JavaScript
C#
C
Problem: 65.有效数字

构造DFA状态转换表

  1. 写出正规式。
      2. d = 0|1|2|3|4|5|6|7|8|9
(-|+|)(dd*(.d*|)|d*.dd*)((e|E)(-|+|)dd*|)
  1. 根据正规式画出 NFA。
      2. ---
title: nfa
---
%%{init: { 'theme': 'base' }}%%
stateDiagram
  direction LR
  [*] --> 0
  0 --> 1: -|+|ε
  1 --> 2: dd*(.d*|)|d*.dd*
  2 --> 3: (e|E)(-|+|ε)dd*|ε
  3 --> [*]
      %%{init: { 'theme': 'base' }}%%
stateDiagram
  direction LR
  [*] --> 0
  0 --> 1: -
  0 --> 1: +
  0 --> 1: ε
  1 --> 2: dd*(.d*|)
  1 --> 2: d*.dd*
  2 --> 3: (e|E)(-|+|ε)dd*
  2 --> 3: ε
  3 --> [*]
      %%{init: { 'theme': 'base' }}%%
stateDiagram
  direction LR
  [*] --> 0
  0 --> 1: -
  0 --> 1: +
  0 --> 1: ε
  1 --> 1_1: dd*
  1_1 --> 2: .d*
  1_1 --> 2: ε
  1 --> 2: d*.dd*
  2 --> 2_1: e|E
  2_1 --> 2_2: -|+|ε
  2_2 --> 3: dd*
  2 --> 3: ε
  3 --> [*]
      %%{init: { 'theme': 'base' }}%%
stateDiagram
  direction LR
  [*] --> 0
  0 --> 1: -
  0 --> 1: +
  0 --> 1: ε
  1 --> 1_1_1: d
  1_1_1 --> 1_1_1: d
  1_1_1 --> 1_1: ε
  1_1 --> 1_1_2: .
  1_1_2 --> 1_1_2: d
  1_1_2 --> 2: ε
  1_1 --> 2: ε
  1 --> 1_2: ε
  1_2 --> 1_2: d
  1_2 --> 1_3: .
  1_3 --> 1_4: d
  1_4 --> 1_4: d
  1_4 --> 2: ε
  2 --> 2_1: e
  2 --> 2_1: E
  2_1 --> 2_2: -
  2_1 --> 2_2: +
  2_1 --> 2_2: ε
  2_2 --> 2_2_1: d
  2_2_1 --> 2_2_1: d
  2_2_1 --> 3: ε
  2 --> 3: ε
  3 --> [*]
      %%{init: { 'theme': 'base' }}%%
stateDiagram
  direction LR
  [*] --> 0
  0 --> 1: -
  0 --> 1: +
  0 --> 1: ε
  1 --> 2: d
  2 --> 2: d
  2 --> 3: ε
  3 --> 4: .
  4 --> 4: d
  4 --> 8: ε
  3 --> 8: ε
  1 --> 5: ε
  5 --> 5: d
  5 --> 6: .
  6 --> 7: d
  7 --> 7: d
  7 --> 8: ε
  8 --> 9: e
  8 --> 9: E
  9 --> 10: -
  9 --> 10: +
  9 --> 10: ε
  10 --> 11: d
  11 --> 11: d
  11 --> 12: ε
  8 --> 12: ε
  12 --> [*]
  1. NFA 确定化（NFA DFA）。
      2. ㅤ
      -
      +
      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}
      ㅤ
      ㅤ
      ㅤ
  1. DFA 最小化（已无法最小化）。

表驱动法具体实现

  1. 写出 DFA 状态转换表。
      2. ㅤ
      '-'
      '+'
      '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*
      ㅤ
      ㅤ
      ㅤ
  1. 各状态对于 -/+ 和 e/E 的转换动作一致，为了节省数组空间，对该表进一步简化。
      2. ㅤ
      '-'/'+'
      '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;
    }
}
C#
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;
        }
    }
}
C
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;
}

复杂度分析

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