Ming
0%

LeetCode-65

Posted on Edited on In

题目

65. 有效数字

代码

利用Java的Parse

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isNumber(String s) {
        try {
            if (s.endsWith("f") || s.endsWith("D")) {
                return false;
            }
            Double.parseDouble(s);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }
}

DFA (Deterministic Finite Automaton）

在计算理论中，确定有限状态自动机或确定有限自动机（英语：deterministic finite automaton, DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表Σ的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态可以是先前那个状态)。

DFA可以接受的字符：

  1. Number
  2. Dot
  3. +-
  4. E/e

DFA存在若干种状态，从初态开始，根据DFA接收的字符跳转到不同的状态。

题目给定的数字存在很多可以接受的状态，这些形态构成了DFA的终态。

所有可识别的字符串都能从初态找到一条通往终态的路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
package main

import (
	"fmt"
	"unicode"
)

func main() {
	fmt.Println(isNumber("53.5e93"))
	fmt.Println(isNumber("abc"))
	fmt.Println(isNumber("95a54e53"))
	fmt.Println(isNumber(".1"))
	fmt.Println(isNumber("3."))
	fmt.Println(isNumber("2e0"))
	fmt.Println(isNumber("46.e3"))
}

type CharacterType int
type State int

const (
	Number CharacterType = iota
	Dot
	PlusMinus
	E
	Unknown
)

const (
	state0 State = iota
	state1
	state2
	state3
	state4
	state5
	state6
	state7
	state8
)

var Transform = map[State]map[CharacterType]State{
	state0: {
		PlusMinus: state1,
		Number:    state2,
		Dot:       state3,
	},
	state1: {
		Number: state2,
		Dot:    state3,
	},
	state2: {
		Number: state2,
		Dot:    state4,
		E:      state6,
	},
	state3: {
		Number: state5,
	},
	state4: {
		Number: state5,
		E:      state6,
	},
	state5: {
		Number: state5,
		E:      state6,
	},
	state6: {
		PlusMinus: state7,
		Number:    state8,
	},
	state7: {
		Number: state8,
	},
	state8: {
		Number: state8,
	},
}

func isNumber(s string) bool {
	state := state0
	for _, v := range s {
		ct := getType(v)
		if ct == Unknown {
			return false
		}
		if next, ok := Transform[state][ct]; !ok {
			return false
		} else {
			state = next
		}
	}
	return state == state2 || state == state4 || state == state5 || state == state8
}

func getType(ch rune) CharacterType {
	if unicode.IsDigit(ch) {
		return Number
	}
	if ch == '.' {
		return Dot
	}
	if ch == '+' || ch == '-' {
		return PlusMinus
	}
	if ch == 'e' || ch == 'E' {
		return E
	}
	return Unknown
}