关注Java领域相关技术 记录有趣的事情

剑指 Offer 20. 表示数值的字符串

US-B.Ralph
US-B.Ralph
2020-09-02

问题地址

LeetCode每日一题/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的后边可以是数字也可以是符号

复杂度分析

  1. 时间复杂度,O(n),其中 n 是字符串去掉首尾空格后的长度。
  2. 空间复杂度,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++ 文档而言,本题还有一点额外的不同,即允许字符串首末两端有一些额外的空格。
  • 在上面描述的五个部分中,每个部分都不是必需的,但也受一些额外规则的制约,如:
    • 如果符号位存在,其后面必须跟着数字或小数点。
    • 小数点的前后两侧,至少有一侧是数字。
思路与算法
  • 根据上面的描述,现在可以定义自动机的「状态集合」了。那么怎么挖掘出所有可能的状态呢?一个常用的技巧是,用「当前处理到字符串的哪个部分」当作状态的表述。根据这一技巧,不难挖掘出所有状态:
    1. 起始的空格
    2. 符号位
    3. 整数部分
    4. 左侧有整数的小数点
    5. 左侧无整数的小数点(根据前面的第二条额外规则,需要对左侧有无整数的两种小数点做区分)
    6. 小数部分
    7. 字符 \text{e}
    8. 指数部分的符号位
    9. 指数部分的整数部分
    10. 末尾的空格
  • 下一步是找出「初始状态」和「接受状态」的集合。根据题意,「初始状态」应当为状态 1,而「接受状态」的集合则为状态 3、状态 4、状态 6、状态 9 以及状态 10。换言之,字符串的末尾要么是空格,要么是数字,要么是小数点,但前提是小数点的前面有数字。
  • 最后,需要定义「转移规则」。结合数值字符串应当具备的格式,将自动机转移的过程以图解的方式表示出来:

  • 比较上图与「预备知识」一节中对自动机的描述,可以看出有一点不同:

    • 我们没有单独地考虑每种字符,而是划分为若干类。由于全部 10 个数字字符彼此之间都等价,因此只需定义一种统一的「数字」类型即可。对于正负号也是同理。
  • 在实际代码中,我们需要处理转移失败的情况。例如当位于状态 1(起始空格)时,没有对应字符 \text{e} 的状态。为了处理这种情况,我们可以创建一个特殊的拒绝状态。如果当前状态下没有对应读入字符的「转移规则」,我们就转移到这个特殊的拒绝状态。一旦自动机转移到这个特殊状态,我们就可以立即判定该字符串不「被接受」。

复杂度分析:
  1. 时间复杂度,O(N),其中 N 为字符串的长度。我们需要遍历字符串的每个字符,其中状态转移所需的时间复杂度为 O(1)
  2. 空间复杂度,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 种状态。
    1. 开始的空格
    2. 幂符号前的正负号
    3. 小数点前的数字
    4. 小数点、小数点后的数字
    5. 当小数点前为空格时,小数点、小数点后的数字
    6. 幂符号
    7. 幂符号后的正负号
    8. 幂符号后的数字
    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]
  • 返回值: 跳出循环后,若状态 p∈{2,3,7,8} ,说明结尾合法,返回 True ,否则返回 False。

复杂度分析:

  1. 时间复杂度,O(N),其中 N 为字符串的长度。判断需要遍历字符串,每次状态转移得使用 O(1)时间。
  2. 空间复杂度,O(1)statesp 使用常数大小的额外空间。

代码:

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;
    }
}
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

7 + 4 =