LeetCode 065 Valid Number

LeetCode

<div>

A valid number can be split up into these components (in order):

1. A decimal number or an integer.
2. (Optional) An 'e' or 'E', followed by an integer.

A decimal number can be split up into these components (in order):

1. (Optional) A sign character (either '+' or '-').
2. One of the following formats:
   1. One or more digits, followed by a dot '.'.
   2. One or more digits, followed by a dot '.', followed by one or more digits.
   3. A dot '.', followed by one or more digits.

An integer can be split up into these components (in order):

1. (Optional) A sign character (either '+' or '-').
2. One or more digits.

For example, all the following are valid numbers: ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"], while the following are not valid numbers: ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"].

Given a string s, return true if s is a valid number.

Example 1:

<pre>Input: s = "0" Output: true </pre>

Example 2:

<pre>Input: s = "e" Output: false </pre>

Example 3:

<pre>Input: s = "." Output: false </pre>

Constraints:

• 1 <= s.length <= 20
• s consists of only English letters (both uppercase and lowercase), digits (0-9), plus '+', minus '-', or dot '.'.

</div>

题目大意：

求合法小数指数形式

类括号法解题思路(推荐)：

有四种symbol，要保证先后关系。

解题步骤：

1. 先写基本框架：

   def isNumber(self, s: str) -> bool:
   	seen_sign, seen_num, seen_exp, seen_dot = False, False, False, False
   	for char in s:
   		if char = '+-':
   			if seen_sign:
   				return False
   			seen_sign = True
   		elif char.isdigit():
   
   			seen_num = True
   		elif char in 'eE':
   			if seen_exp:
   				return False
   			seen_exp = True
   		elif char == '.':
   			if seen_dot:
   				return False
   			seen_dot = True
   		else:
   			return False
   	return True

2. if语句加入前面字符不能出现什么，每种其他字符过一遍。还有字符必须出现什么，此情况只有一种： e字符前必须有数字
3. for循环后return语句检查单个字符

注意事项：

1. 有四种symbol： 符号，数字，dot，exp。保证先后关系。exp的前后部分是独立的，唯一区别是后部分不能有dot，如1e2.2
2. 实现类似于括号题用if语句来分别处理每种symbol：前面不能出现什么符号(e后面不能出现小数，也就是小数前面不能出现e)，或必须出现什么符号(仅一种情况：e前面必须出现数字)，如1e2. 然后该符号赋True
3. for循环后检查单个字符且不含数字情况 见解题步骤

Python代码：

def isNumber(self, s: str) -> bool:
	seen_sign, seen_num, seen_exp, seen_dot = False, False, False, False
	for char in s:
		if char in '+-':
			if seen_sign or seen_num or seen_dot:
				return False
			seen_sign = True
		elif char.isdigit():
			seen_num = True
		elif char in 'eE':
			if seen_exp or not seen_num:
				return False
			seen_exp = True
			seen_sign = False
			seen_num = False
			seen_dot = False
		elif char == '.':
			if seen_dot or seen_exp:
				return False
			seen_dot = True
		else:
			return False
	return False if (seen_sign or seen_exp or seen_dot) and not seen_num else True

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

---

DFA算法II解题思路(不推荐)：

Deterministic Finite Automaton (DFA)状态机，也就是将状态写入一个map中作为config，代码较简洁，但很难想。

算法分析：

时间复杂度为O(n)，空间复杂度O(1)