KK's blog

每天积累多一些

0%

LeetCode 065 Valid Number

Posted on Edited on Disqus:

LeetCode



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:

Input: s = “0”
Output: true


Example 2:

Input: s = “e”
Output: false


Example 3:

Input: s = “.”
Output: false


Constraints:

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

题目大意：

求合法小数指数形式

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

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

解题步骤：

  1. 先写基本框架：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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)

Free mock interview