Leetcode - Valid Number Solution

A numeric string can include a sign, a decimal point, and an exponent. Their positions determine whether the string is valid. I tried four approaches before settling on the clearest one.

The problem asks us to validate strings like "2", "-0.1", "4.", "2e10" while rejecting "abc", "1e", "99e2.5", and other invalid formats. The four approaches expose different trade offs between brevity, explicit state, and maintainability.

Valid number formats

The input grammar has two groups of examples:

These should work:

• Simple integers: "2", "0089"
• Numbers with signs: "-0.1", "+3.14"
• Decimal numbers: "4.", "-.9", ".1"
• Numbers with exponents: "2e10", "-90E3", "3e+7"

These should not:

• "abc": contains no digits
• "1e": exponent without digits
• "99e2.5": cannot have decimal after exponent
• "--6": multiple signs do not make sense
• "1a", "e3", "95a54e53": mixing valid and invalid characters

First attempt: Regex

I started with a regular expression because the format looks like a pattern matching problem.

The first version was:

function isValidNumberNaive(s) {
  const pattern = /^\s*[+-]?(\d+\.?\d*|\.\d+)([eE][+-]?\d+)?\s*$/;
  return pattern.test(s);
}

It matched the initial examples. The pattern breaks down as follows:

• ^\s*: Skip leading whitespace
• [+-]?: Optional plus or minus
• (\d+\.?\d*|\.\d+): The number part (either digits with optional decimal, OR decimal with digits)
• ([eE][+-]?\d+)?: Optional exponent part
• \s*$: Skip trailing whitespace

The pattern is compact, but its rules are hard to inspect. A requirements change would make me examine each quantifier and alternative again. A failed match would also be difficult to diagnose.

New edge cases would make that trade off worse because each change would add another branch to a pattern that is already difficult to read.

Performance Analysis: Regex Approach

A short pattern does not guarantee a linear scan. V8 explains how its backtracking engine retries alternatives after a failed match.

Time Complexity: Potentially O(n²) with backtracking

In this pattern, \d+ and \d* can both consume the same digit sequence when the optional decimal point is absent. A long digit sequence followed by an invalid character can make the engine retry many divisions of those digits. Engine optimizations or another matching algorithm can change that behavior.

Space Complexity: Engine dependent

The pattern passed to .test() has constant size, but that does not establish the matcher's working memory. The engine may keep backtracking state.

The explicit parsers below make their linear scan easier to verify.

Second attempt: Explicit parsing

I then wrote the same grammar as explicit parsing steps:

function isValidNumberBetter(s) {
  // Step 1: Skip leading whitespace
  let i = 0;
  while (i < s.length && s[i] === " ") i++;
  if (i >= s.length) return false;

  // Step 2: Check for optional sign
  if (s[i] === "+" || s[i] === "-") i++;

  let hasNumber = false;
  let hasDot = false;

  // Step 3: Parse digits before decimal
  while (i < s.length && /[0-9]/.test(s[i])) {
    hasNumber = true;
    i++;
  }

  // Step 4: Parse optional decimal part
  if (i < s.length && s[i] === ".") {
    hasDot = true;
    i++;
    while (i < s.length && /[0-9]/.test(s[i])) {
      hasNumber = true;
      i++;
    }
  }

  // Step 5: We need at least one digit
  if (!hasNumber) return false;

  // Step 6: Parse optional exponent
  if (i < s.length && (s[i] === "e" || s[i] === "E")) {
    i++;
    if (i < s.length && (s[i] === "+" || s[i] === "-")) i++;

    let exponentHasNumber = false;
    while (i < s.length && /[0-9]/.test(s[i])) {
      exponentHasNumber = true;
      i++;
    }

    if (!exponentHasNumber) return false;
  }

  // Step 7: Skip trailing whitespace
  while (i < s.length && s[i] === " ") i++;

  return i === s.length;
}

The parser first skips spaces and reads an optional sign. It then parses the number, decimal part, and exponent. A final check rejects any remaining characters. The examples passed, but I found the separate phases difficult to follow as one validation rule.

Performance Analysis: Step by Step Approach

The explicit parser's complexity is:

Time Complexity: O(n)

• I use a single index i that moves from start to end of the string
• Each character is examined exactly once
• No nested loops that would multiply the work
• The while loops are sequential, not nested

Space Complexity: O(1)

• I only use a few boolean variables (hasNumber, hasDot) and integers (i)
• These do not scale with input size. They use constant space
• No arrays or data structures that grow with the input

It remains O(n) time and O(1) space, while making each validation step visible. That visibility makes debugging and future changes easier.

Third attempt: State machine

I was reading about formal methods, so I modeled the grammar as a state machine. Each character moves to a new state, and only certain states can end a valid number.

The resulting state machine was:

function isValidNumberOptimized(s) {
  // Define all possible states
  const State = {
    START: 0, // Initial state
    SIGN: 1, // Just read a sign
    INTEGER: 2, // Reading integer digits
    DOT: 3, // Just read a dot
    DECIMAL: 4, // Reading decimal digits
    EXPONENT: 5, // Just read exponent
    EXPONENT_SIGN: 6, // Reading exponent sign
    EXPONENT_NUMBER: 7, // Reading exponent digits
    END: 8, // Valid ending state
  };

  // Define state transitions
  const transitions = {
    [State.START]: {
      digit: State.INTEGER,
      "+": State.SIGN,
      "-": State.SIGN,
      ".": State.DOT,
      " ": State.START,
    },
    [State.SIGN]: {
      digit: State.INTEGER,
      ".": State.DOT,
    },
    [State.INTEGER]: {
      digit: State.INTEGER,
      ".": State.DECIMAL,
      e: State.EXPONENT,
      E: State.EXPONENT,
      " ": State.END,
    },
    [State.DOT]: {
      digit: State.DECIMAL,
    },
    [State.DECIMAL]: {
      digit: State.DECIMAL,
      e: State.EXPONENT,
      E: State.EXPONENT,
      " ": State.END,
    },
    [State.EXPONENT]: {
      digit: State.EXPONENT_NUMBER,
      "+": State.EXPONENT_SIGN,
      "-": State.EXPONENT_SIGN,
    },
    [State.EXPONENT_SIGN]: {
      digit: State.EXPONENT_NUMBER,
    },
    [State.EXPONENT_NUMBER]: {
      digit: State.EXPONENT_NUMBER,
      " ": State.END,
    },
    [State.END]: {
      " ": State.END,
    },
  };

  let currentState = State.START;

  // Process each character
  for (let char of s) {
    let charType = "";

    // Categorize the character
    if (char >= "0" && char <= "9") {
      charType = "digit";
    } else if (char === "+" || char === "-") {
      charType = char;
    } else if (char === ".") {
      charType = ".";
    } else if (char === "e" || char === "E") {
      charType = "e";
    } else if (char === " ") {
      charType = " ";
    } else {
      return false;
    }

    // Check if transition is valid
    if (
      !transitions[currentState] ||
      !Object.prototype.hasOwnProperty.call(transitions[currentState], charType)
    ) {
      return false;
    }

    // Move to next state
    currentState = transitions[currentState][charType];
  }

  // Check if we ended in a valid state
  return [
    State.INTEGER,
    State.DECIMAL,
    State.EXPONENT_NUMBER,
    State.END,
  ].includes(currentState);
}

The table makes the allowed transitions explicit. Each state represents what has appeared so far, and each transition defines what can come next.

Implementing it was harder than expected. The transition table was cumbersome to maintain, and failures were harder to localize than in the explicit parser.

The result was a useful trade off: a mathematically tidy model can still be a poor fit for a small grammar.

Performance Analysis: State Machine Approach

The state machine's complexity is:

Time Complexity: O(n)

• I process each character exactly once in the main for loop
• Each character categorization and state transition is O(1)
• The final state check with .includes() is O(1) since it is checking a fixed array of 4 states
• Overall: n characters × O(1) operations = O(n)

Space Complexity: O(1)

• The State object and transitions object are constant size (9 states, fixed number of transitions)
• currentState is a number
• charType is a string, but its length is bounded (max "EXPONENT_NUMBER" which is constant)
• Even though I create these objects once, they do not grow with input size

Trade offs:

• Pros: Explicit transitions and a fixed set of states
• Cons: More code and indirection than this grammar needs, with failures spread across the transition table
• When it helps: When validation rules have enough states that a transition table clarifies them

The scan remains O(n). This comparison does not include a runtime benchmark, so the decision rests on readability and the amount of state the rules require.

Final solution: Boolean flags

The final implementation tracks four facts about the input with boolean flags. That keeps the rules visible without the transition table from the previous attempt.

function isValidNumber(s) {
  // Remove leading and trailing whitespace
  s = s.trim();

  // Track what we've seen with simple boolean flags
  let seenDigit = false; // Have we seen any digits?
  let seenDot = false; // Have we seen a decimal point?
  let seenE = false; // Have we seen an exponent?
  let digitAfterE = true; // Do we have digits after the exponent?

  for (let i = 0; i < s.length; i++) {
    const currentChar = s[i];

    if (/[0-9]/.test(currentChar)) {
      // Found a digit
      seenDigit = true;
      if (seenE) {
        // If we're after an exponent, mark that we have digits
        digitAfterE = true;
      }
    } else if (currentChar === "+" || currentChar === "-") {
      // Sign can only appear at start or right after 'e'/'E'
      if (i > 0 && s[i - 1] !== "e" && s[i - 1] !== "E") {
        return false;
      }
    } else if (currentChar === ".") {
      // Can't have multiple dots or dots after exponent
      if (seenDot || seenE) return false;
      seenDot = true;
    } else if (currentChar === "e" || currentChar === "E") {
      // Can't have multiple exponents or exponent without digits
      if (seenE || !seenDigit) return false;
      seenE = true;
      digitAfterE = false; // Reset flag for exponent part
    } else {
      // Any other character is invalid
      return false;
    }
  }

  // Valid if: we saw digits AND (no exponent OR digits after exponent)
  return seenDigit && digitAfterE;
}

Each flag records one condition, and the loop makes one pass. I can add a validation rule without a change to a transition table. The implementation passes the shared 32-case suite used to verify the examples.

Performance Analysis: Boolean Flags Approach (Final Solution)

The implementation's complexity follows from the code:

Time Complexity: O(n)

• I iterate through each character exactly once with the for loop
• All operations inside the loop are O(1): comparisons, assignments, boolean checks
• The .trim() operation is O(n), but that is dominated by the main O(n) loop
• Total: O(n) + O(n) = O(n)

Space Complexity: O(n) in this implementation

• The parser state uses 4 boolean variables and one loop index, so that part is O(1)
• s.trim() can allocate a normalized copy of the input, which takes O(n) extra space in the worst case
• An index based trim could keep the parser state and the overall extra space at O(1), but that is not the implementation shown here

What this version guarantees:

1. Linear time: You cannot do better than O(n) because you need to examine each character
2. Bounded parser state: The flags and loop index stay O(1), even though trim() makes this implementation O(n) extra space in the worst case

Complexity Comparison Summary

The approaches compare as follows:

The approaches differ in how they represent the grammar and allocate memory. The boolean flags approach has the clearest parser state, while its trim() call adds O(n) extra space in the worst case.

Valid and invalid input tests

These examples cover the main valid and invalid forms:

const testCases = [
  { input: "0", expected: true },
  { input: "e", expected: false },
  { input: ".", expected: false },
  { input: " 0 ", expected: true },
  { input: " 0.1 ", expected: true },
  { input: "2e10", expected: true },
  { input: "abc", expected: false },
  { input: "1a", expected: false },
  { input: "1e", expected: false },
  { input: "99e2.5", expected: false },
];

testCases.forEach(({ input, expected }) => {
  const result = isValidNumber(input);
  console.log(
    `"${input}" -> ${result} (expected ${expected}) ${
      result === expected ? "✓" : "✗"
    }`
  );
});

The sample cases pass. The traces below show why:

Example 1: "2e10" (should be valid)

• Start: seenDigit=false, seenDot=false, seenE=false, digitAfterE=true
• '2' → seenDigit = true
• 'e' → seenE = true, digitAfterE = false (reset for exponent)
• '1' → seenDigit = true, digitAfterE = true (found digit after exponent)
• '0' → seenDigit = true, digitAfterE = true
• End: seenDigit=true AND digitAfterE=true → return true ✓

Example 2: "1e" (should be invalid)

• Start: seenDigit=false, seenDot=false, seenE=false, digitAfterE=true
• '1' → seenDigit = true
• 'e' → seenE = true, digitAfterE = false (reset for exponent)
• End: seenDigit=true AND digitAfterE=false → return false ✗

Example 3: "99e2.5" (should be invalid)

• Start: seenDigit=false, seenDot=false, seenE=false, digitAfterE=true
• '9' → seenDigit = true
• '9' → seenDigit = true
• 'e' → seenE = true, digitAfterE = false
• '2' → seenDigit = true, digitAfterE = true
• '.' → return false immediately (cannot have decimal after exponent) ✗

Key takeaways

1. A working solution is not automatically maintainable. The regex passed the examples, but the explicit approaches made the validation rules easier to inspect and change.

2. Formal structure has a cost. A state machine can clarify complex transitions, but four flags are enough for this grammar and require less machinery.

3. Readable state makes debugging local. Each flag describes one invariant, so an invalid input can be traced to the rule that rejected it.

4. Big O does not describe every implementation detail. The explicit parsers scan in O(n) time. The regex can backtrack. The final parser uses O(n) extra space if trim() allocates a normalized string. The parser state itself remains O(1).

For this problem, the boolean flags parser is the version I would keep. It exposes the rules, passes the tests, and leaves room for changes without hiding behavior behind a pattern or transition table.