Valid Number

描述

Validate if a given string is numeric.

Some examples:

  1. "0" => true
  2. " 0.1 " => true
  3. "abc" => false
  4. "1 a" => false
  5. "2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

分析

细节实现题。

本题的功能与标准库中的strtod()功能类似。

有限自动机

  1. // Valid Number
  2. // finite automata，时间复杂度O(n)，空间复杂度O(n)
  3. public class Solution {
  4.     public boolean isNumber(String s) {
  5.         int[][] transitionTable  = new int[][] {
  6.             { -1, 0, 3, 1, 2, -1 }, // next states for state 0
  7.             { -1, 8, -1, 1, 4, 5 },     // next states for state 1
  8.             { -1, -1, -1, 4, -1, -1 },     // next states for state 2
  9.             { -1, -1, -1, 1, 2, -1 },     // next states for state 3
  10.             { -1, 8, -1, 4, -1, 5 },     // next states for state 4
  11.             { -1, -1, 6, 7, -1, -1 },     // next states for state 5
  12.             { -1, -1, -1, 7, -1, -1 },     // next states for state 6
  13.             { -1, 8, -1, 7, -1, -1 },     // next states for state 7
  14.             { -1, 8, -1, -1, -1, -1 }     // next states for state 8
  15.         };
  17.         int state = 0;
  18.         for (int i = 0; i < s.length(); ++i) {
  19.             final char ch = s.charAt(i);
  20.             InputType inputType = InputType.INVALID;
  22.             if (Character.isSpaceChar(ch))
  23.                 inputType = InputType.SPACE;
  24.             else if (ch == '+' || ch == '-')
  25.                 inputType = InputType.SIGN;
  26.             else if (Character.isDigit(ch))
  27.                 inputType = InputType.DIGIT;
  28.             else if (ch == '.')
  29.                 inputType = InputType.DOT;
  30.             else if (ch == 'e' || ch == 'E')
  31.                 inputType = InputType.EXPONENT;
  33.             // Get next state from current state and input symbol
  34.             state = transitionTable[state][inputType.ordinal()];
  36.             // Invalid input
  37.             if (state == -1) return false;
  38.         }
  39.         // If the current state belongs to one of the accepting (final) states,
  40.         // then the number is valid
  41.         return state == 1 || state == 4 || state == 7 || state == 8;
  43.     }
  44.     enum InputType {
  45.         INVALID,    // 0
  46.         SPACE,      // 1
  47.         SIGN,       // 2
  48.         DIGIT,      // 3
  49.         DOT,        // 4
  50.         EXPONENT,   // 5
  51.         NUM_INPUTS  // 6
  52.     }
  53. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/string/valid-number.html