题目链接

LeetCode

题目描述

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”、”5e2”、”-123”、”3.1416”、”-1E-16”、”0123”都表示数值，但”12e”、”1a3.14”、”1.2.3”、”+-5”及”12e+5.4”都不是。

  1. true
  3. "+100"
  4. "5e2"
  5. "-123"
  6. "3.1416"
  7. "-1E-16"
  9. false
  11. "12e"
  12. "1a3.14"
  13. "1.2.3"
  14. "+-5"
  15. "12e+4.3"

解题思路

方法一：使用正则表达式进行匹配。

[]  ： 字符集合
()  ： 分组
?   ： 重复 0 ~ 1 次
+   ： 重复 1 ~ n 次
*   ： 重复 0 ~ n 次
.   ： 任意字符
\\. ： 转义后的 .
\\d ： 数字
// 数字的格式可以用A[.[B]][e|EC]或者.B[e|EC]表示，
// 其中A和C都是整数（可以有正负号，也可以没有），而B是一个无符号整数
import java.util.regex.Pattern;
public boolean isNumeric(char[] str) {
    if (str == null || str.length == 0)
        return false;
    return new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?");
}
  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度

  • 空间复杂度：O(1)

    方法二：依次分析

    数字的格式可以用A[.[B]][e|EC]或者.B[e|EC]表示，
    其中A和C都是整数（可以有正负号，也可以没有），而B是一个无符号整数
    指数只能是整数，并且小数点后不能有正负号。

    class Solution {
private:
  // 整数的格式可以用[+|-]B表示, 其中B为无符号整数
  bool scanInteger(const string s, int& index){

      if(s[index] == '+' || s[index] == '-')
          ++index;

      return scanUnsignedInteger(s, index);
  }

  bool scanUnsignedInteger(const string s, int& index){

      int befor = index;
      while(index != s.size() && s[index] >= '0' && s[index] <= '9')
          index ++;

      return index > befor;
  }
public:
  // 数字的格式可以用A[.[B]][e|EC]或者.B[e|EC]表示，
  // 其中A和C都是整数（可以有正负号，也可以没有），而B是一个无符号整数
  // 指数只能是整数
  bool isNumber(string s) {

      if(s.size() == 0)
          return false;
      int index = 0;

      //字符串开始有空格，可以返回true
      while(s[index] == ' ')  //书中代码没有该项测试
          ++index;

      bool numeric = scanInteger(s, index);

      // 如果出现'.'，接下来是数字的小数部分
      if(s[index] == '.'){

          ++index;

          // 下面一行代码用||的原因：
          // 1. 小数可以没有整数部分，例如.123等于0.123；
          // 2. 小数点后面可以没有数字，例如233.等于233.0；
          // 3. 当然小数点前面和后面可以有数字，例如233.666
          // 4.下面scanUnsignedInteger(s, index)必须在前，因为他必须运行函数判断，如果numeric在前
          // 且为true，scanUnsignedInteger(s, index)不运行，pos不向前走
          numeric = scanUnsignedInteger(s, index) || numeric;
      }

      // 如果出现'e'或者'E'，接下来跟着的是数字的指数部分
      if(s[index] == 'e' || s[index] == 'E'){

          ++index;

          // 下面一行代码用&&的原因：
          // 1. 当e或E前面没有数字时，整个字符串不能表示数字，例如.e1、e1；
          // 2. 当e或E后面没有整数时，整个字符串不能表示数字，例如12e、12e+5.4
          numeric = numeric && scanInteger(s ,index);
      }

      //字符串结尾有空格，可以返回true
      while(s[index] == ' ')
          ++index;
      return numeric && index == s.size();
  }
};

  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度

  • 空间复杂度：O(1)

    方法三：有限状态自动机