剑指 Offer 20. 表示数值的字符串
2020-09-02
问题地址
剑指 Offer 20. 表示数值的字符串
问题描述
规则
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100″、”5e2″、”-123″、”3.1416″、”-1E-16″、”0123″都表示数值，但”12e”、”1a3.14″、”1.2.3″、”+-5″及”12e+5.4″都不是。
解析
解题思路
- 根据分析可以整理出如下规则（去掉了首尾的空格）：
- 只有1位时，只能是数字
- 符号位可以出现在首位或者e的后边
- 首位是符号位，后边可以是.也可以是数字
- 非首位出现符号位，符号位前边只能是e
- 小数点和e均只能出现一次
- 小数点只能出现在e后边
- 小数点出现在第一位，后边必须跟数字
- 首尾不可以是e/E
- e的后边可以是数字也可以是符号
复杂度分析
- 时间复杂度，O(n)，其中 n 是字符串去掉首尾空格后的长度。
- 空间复杂度，O(1)。需要若干变量存储中间变量及特定字符（非必须）。
数据操作分析
- 根据规则处理字符串
编码实现
/**
* Offer20
* LeetCode1604
*/
public class Offer0020_BiaoShiShuZiDeZiFuChuan {
private static final char PLUS_SIGN = '+';
private static final char MINUS_SIGN = '-';
private static final char EXP_UPPER_CASE = 'E';
private static final char EXP_LOWER_CASE = 'e';
private static final char DECIMAL_POINT = '.';
private static final char CHAR_ZERO = '0';
private static final char CHAR_NINE = '9';
public boolean isNumber(String s) {
if (s == null || s.equals("")) return false;
s = s.trim();
if (s.equals("")) return false;
char[] chars = s.toCharArray();
int len = chars.length;
boolean isHavePoint = false;
boolean isHaveExp = false;
//只有1位时，只能是数字
if (len == 1) {
if (chars[0] >= CHAR_ZERO && chars[0] <= CHAR_NINE) return true;
return false;
}
//首尾不可以是e
if (chars[0] == EXP_LOWER_CASE || chars[0] == EXP_UPPER_CASE) return false;
if (chars[len - 1] == EXP_LOWER_CASE || chars[len - 1] == EXP_UPPER_CASE) return false;
for (int i = 0; i < len; i++) {
//符号位可以出现在首位或者e的后边
if ((chars[i] == PLUS_SIGN || chars[i] == MINUS_SIGN)) {
if (i == (len - 1)) return false;
//首位是符号位，后边可以是.也可以是数字
if (i == 0 && !(chars[i + 1] >= CHAR_ZERO && CHAR_NINE >= chars[i + 1]) && !(chars[i + 1] == DECIMAL_POINT))
return false;
//非首位出现符号位，符号位前边只能是e
if (i > 0 && !(chars[i - 1] == EXP_LOWER_CASE || chars[i - 1] == EXP_UPPER_CASE)) return false;
continue;
}
//小数点只能出现一次
if (chars[i] == DECIMAL_POINT && isHavePoint) return false;
//小数点只能出现在e后边
if (chars[i] == DECIMAL_POINT && !isHavePoint && !isHaveExp) {
//小数点出现在第一位，后边必须跟数字
if (i == 0) {
if (!(chars[i + 1] >= CHAR_ZERO && CHAR_NINE >= chars[i + 1])) return false;
} else if (i == chars.length - 1) {//小数点出现在最后一位后边必须跟数字
if (!(chars[i - 1] >= CHAR_ZERO && CHAR_NINE >= chars[i - 1])) return false;
//非首位、非末尾，小数点前必须是数字,后边可以是e或数字
} else if (!(chars[i + 1] >= CHAR_ZERO && CHAR_NINE >= chars[i + 1]) &&
!(chars[i + 1] == EXP_LOWER_CASE || chars[i + 1] == EXP_UPPER_CASE) &&
!(chars[i - 1] >= CHAR_ZERO && CHAR_NINE >= chars[i - 1]))
return false;
isHavePoint = true;
continue;
}
if ((chars[i] == EXP_LOWER_CASE || chars[i] == EXP_UPPER_CASE) && isHaveExp) return false;
//e的前边只能是数字
//e的后边可以是数字也可以是符号
if ((chars[i] == EXP_LOWER_CASE || chars[i] == EXP_UPPER_CASE) && !isHaveExp && len >= 3) {
if (!(chars[i - 1] >= CHAR_ZERO && chars[i - 1] <= CHAR_NINE) && !(chars[i - 1] == DECIMAL_POINT))
return false;
if (!(chars[i + 1] >= CHAR_ZERO && chars[i + 1] <= CHAR_NINE) && !(chars[i + 1] == PLUS_SIGN || chars[i + 1] == MINUS_SIGN))
return false;
isHaveExp = true;
continue;
}
if (!(chars[i] >= CHAR_ZERO && chars[i] <= CHAR_NINE)) return false;
}
return true;
}
}
官方解法
确定有限状态自动机
预备知识：
- 确定有限状态自动机（以下简称「自动机」）是一类计算模型。它包含一系列状态，这些状态中：
- 有一个特殊的状态，被称作「初始状态」。
- 还有一系列状态被称为「接受状态」，它们组成了一个特殊的集合。其中，一个状态可能既是「初始状态」，也是「接受状态」。
- 起初，这个自动机处于「初始状态」。随后，它顺序地读取字符串中的每一个字符，并根据当前状态和读入的字符，按照某个事先约定好的「转移规则」，从当前状态转移到下一个状态；当状态转移完成后，它就读取下一个字符。当字符串全部读取完毕后，如果自动机处于某个「接受状态」，则判定该字符串「被接受」；否则，判定该字符串「被拒绝」。
- 注意：如果输入的过程中某一步转移失败了，即不存在对应的「转移规则」，此时计算将提前中止。在这种情况下我们也判定该字符串「被拒绝」。
- 一个自动机，总能够回答某种形式的「对于给定的输入字符串 S，判断其是否满足条件 P」的问题。在本题中，条件 P 即为「构成合法的表示数值的字符串」。
- 自动机驱动的编程，可以被看做一种暴力枚举方法的延伸：它穷尽了在任何一种情况下，对应任何的输入，需要做的事情。
- 自动机在计算机科学领域有着广泛的应用。在算法领域，它与大名鼎鼎的字符串查找算法「KMP」算法有着密切的关联；在工程领域，它是实现「正则表达式」的基础。
问题描述
- 在 C++ 文档 中，描述了一个合法的数值字符串应当具有的格式。具体而言，它包含以下部分：
- 符号位，即 ++、-− 两种符号
- 整数部分，即由若干字符 0-90−9 组成的字符串
- 小数点
- 小数部分，其构成与整数部分相同
- 指数部分，其中包含开头的字符 \text{e}e（大写小写均可）、可选的符号位，和整数部分
- 相比于 C++ 文档而言，本题还有一点额外的不同，即允许字符串首末两端有一些额外的空格。
- 在上面描述的五个部分中，每个部分都不是必需的，但也受一些额外规则的制约，如：
- 如果符号位存在，其后面必须跟着数字或小数点。
- 小数点的前后两侧，至少有一侧是数字。
思路与算法
- 根据上面的描述，现在可以定义自动机的「状态集合」了。那么怎么挖掘出所有可能的状态呢？一个常用的技巧是，用「当前处理到字符串的哪个部分」当作状态的表述。根据这一技巧，不难挖掘出所有状态：
- 起始的空格
- 符号位
- 整数部分
- 左侧有整数的小数点
- 左侧无整数的小数点（根据前面的第二条额外规则，需要对左侧有无整数的两种小数点做区分）
- 小数部分
- 字符 \text{e}
- 指数部分的符号位
- 指数部分的整数部分
- 末尾的空格
- 下一步是找出「初始状态」和「接受状态」的集合。根据题意，「初始状态」应当为状态 1，而「接受状态」的集合则为状态 3、状态 4、状态 6、状态 9 以及状态 10。换言之，字符串的末尾要么是空格，要么是数字，要么是小数点，但前提是小数点的前面有数字。
- 最后，需要定义「转移规则」。结合数值字符串应当具备的格式，将自动机转移的过程以图解的方式表示出来：
-
比较上图与「预备知识」一节中对自动机的描述，可以看出有一点不同：
- 我们没有单独地考虑每种字符，而是划分为若干类。由于全部 10 个数字字符彼此之间都等价，因此只需定义一种统一的「数字」类型即可。对于正负号也是同理。
- 在实际代码中，我们需要处理转移失败的情况。例如当位于状态 1（起始空格）时，没有对应字符 \text{e} 的状态。为了处理这种情况，我们可以创建一个特殊的拒绝状态。如果当前状态下没有对应读入字符的「转移规则」，我们就转移到这个特殊的拒绝状态。一旦自动机转移到这个特殊状态，我们就可以立即判定该字符串不「被接受」。
复杂度分析：
- 时间复杂度，O(N)，其中 N 为字符串的长度。我们需要遍历字符串的每个字符，其中状态转移所需的时间复杂度为 O(1)。
- 空间复杂度，O(1)。只需要创建固定大小的状态转移表。
class Solution {
public boolean isNumber(String s) {
Map<State, Map<CharType, State>> transfer = new HashMap<State, Map<CharType, State>>();
Map<CharType, State> initialMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_SPACE, State.STATE_INITIAL);
put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
put(CharType.CHAR_SIGN, State.STATE_INT_SIGN);
}};
transfer.put(State.STATE_INITIAL, initialMap);
Map<CharType, State> intSignMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
}};
transfer.put(State.STATE_INT_SIGN, intSignMap);
Map<CharType, State> integerMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
put(CharType.CHAR_EXP, State.STATE_EXP);
put(CharType.CHAR_POINT, State.STATE_POINT);
put(CharType.CHAR_SPACE, State.STATE_END);
}};
transfer.put(State.STATE_INTEGER, integerMap);
Map<CharType, State> pointMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
put(CharType.CHAR_EXP, State.STATE_EXP);
put(CharType.CHAR_SPACE, State.STATE_END);
}};
transfer.put(State.STATE_POINT, pointMap);
Map<CharType, State> pointWithoutIntMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
}};
transfer.put(State.STATE_POINT_WITHOUT_INT, pointWithoutIntMap);
Map<CharType, State> fractionMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
put(CharType.CHAR_EXP, State.STATE_EXP);
put(CharType.CHAR_SPACE, State.STATE_END);
}};
transfer.put(State.STATE_FRACTION, fractionMap);
Map<CharType, State> expMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
put(CharType.CHAR_SIGN, State.STATE_EXP_SIGN);
}};
transfer.put(State.STATE_EXP, expMap);
Map<CharType, State> expSignMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
}};
transfer.put(State.STATE_EXP_SIGN, expSignMap);
Map<CharType, State> expNumberMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
put(CharType.CHAR_SPACE, State.STATE_END);
}};
transfer.put(State.STATE_EXP_NUMBER, expNumberMap);
Map<CharType, State> endMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_SPACE, State.STATE_END);
}};
transfer.put(State.STATE_END, endMap);
int length = s.length();
State state = State.STATE_INITIAL;
for (int i = 0; i < length; i++) {
CharType type = toCharType(s.charAt(i));
if (!transfer.get(state).containsKey(type)) {
return false;
} else {
state = transfer.get(state).get(type);
}
}
return state == State.STATE_INTEGER || state == State.STATE_POINT || state == State.STATE_FRACTION || state == State.STATE_EXP_NUMBER || state == State.STATE_END;
}
public CharType toCharType(char ch) {
if (ch >= '0' && ch <= '9') {
return CharType.CHAR_NUMBER;
} else if (ch == 'e' || ch == 'E') {
return CharType.CHAR_EXP;
} else if (ch == '.') {
return CharType.CHAR_POINT;
} else if (ch == '+' || ch == '-') {
return CharType.CHAR_SIGN;
} else if (ch == ' ') {
return CharType.CHAR_SPACE;
} else {
return CharType.CHAR_ILLEGAL;
}
}
enum State {
STATE_INITIAL,
STATE_INT_SIGN,
STATE_INTEGER,
STATE_POINT,
STATE_POINT_WITHOUT_INT,
STATE_FRACTION,
STATE_EXP,
STATE_EXP_SIGN,
STATE_EXP_NUMBER,
STATE_END,
}
enum CharType {
CHAR_NUMBER,
CHAR_EXP,
CHAR_POINT,
CHAR_SIGN,
CHAR_SPACE,
CHAR_ILLEGAL,
}
}
精彩评论
跳转地址：面试题20. 表示数值的字符串（有限状态自动机，清晰图解）
思路
- 本题使用有限状态自动机。根据字符类型和合法数值的特点，先定义状态，再画出状态转移图，最后编写代码即可。
字符类型
- 空格 「 」、数字「 0—9 」 、正负号 「 +- 」 、小数点 「 . 」 、幂符号 「 eE 」 。
状态定义
- 按照字符串从左到右的顺序，定义以下 9 种状态。
- 开始的空格
- 幂符号前的正负号
- 小数点前的数字
- 小数点、小数点后的数字
- 当小数点前为空格时，小数点、小数点后的数字
- 幂符号
- 幂符号后的正负号
- 幂符号后的数字
- 结尾的空格
结束状态
合法的结束状态有 2, 3, 7, 8 。
算法流程
- 初始化
- 状态转移表 states ： 设 states[i] ，其中 i 为所处状态，states[i] 使用哈希表存储可转移至的状态。键值对 (key, value) 含义：若输入 key ，则可从状态 i 转移至状态 value 。
- 当前状态 p ： 起始状态初始化为 p = 0 。
- 状态转移循环： 遍历字符串 s 的每个字符 c 。
- 记录字符类型 tt ： 分为四种情况。
- 当 c 为正负号时，执行 t = ‘s’ ;
- 当 c 为数字时，执行 t = ‘d’ ;
- 当 c 为 e , E 时，执行 t = ‘e’ ;
- 当 c 为 . , 空格 时，执行 t = c （即用字符本身表示字符类型）;
- 否则，执行 t = ‘?’ ，代表为不属于判断范围的非法字符，后续直接返回 false 。
- 终止条件： 若字符类型 t 不在哈希表 states[p] 中，说明无法转移至下一状态，因此直接返回 False 。
- 状态转移： 状态 p 转移至 states[p][t] 。
- 记录字符类型 tt ： 分为四种情况。
- 返回值： 跳出循环后，若状态 p∈{2,3,7,8} ，说明结尾合法，返回 True ，否则返回 False。
复杂度分析：
- 时间复杂度，O(N)，其中 N 为字符串的长度。判断需要遍历字符串，每次状态转移得使用 O(1)时间。
- 空间复杂度，O(1)。states 和 p 使用常数大小的额外空间。
。
代码：
class Solution {
public boolean isNumber(String s) {
Map[] states = {
new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
new HashMap<>() {{ put('d', 2); put('.', 4); }}, // 1.
new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }}, // 3.
new HashMap<>() {{ put('d', 3); }}, // 4.
new HashMap<>() {{ put('s', 6); put('d', 7); }}, // 5.
new HashMap<>() {{ put('d', 7); }}, // 6.
new HashMap<>() {{ put('d', 7); put(' ', 8); }}, // 7.
new HashMap<>() {{ put(' ', 8); }} // 8.
};
int p = 0;
char t;
for(char c : s.toCharArray()) {
if(c >= '0' && c <= '9') t = 'd';
else if(c == '+' || c == '-') t = 's';
else if(c == 'e' || c == 'E') t = 'e';
else if(c == '.' || c == ' ') t = c;
else t = '?';
if(!states[p].containsKey(t)) return false;
p = (int)states[p].get(t);
}
return p == 2 || p == 3 || p == 7 || p == 8;
}
}