How do you solve Valid Number on LeetCode?

Valid Number (LeetCode #65) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Understanding number formats is crucial.

What is the brute force solution for Valid Number?

The brute force approach for Valid Number is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves checking every character in the string to determine if it fits the criteria of a valid number. This method is straightforward but inefficient as it may require multiple passes over the string. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Valid Number?

Valid Number uses the following concepts: String. The recommended patterns to study are: Finite State Machine, Regular Expressions.

What are the interview tips for Valid Number?

Explain your thought process clearly. Consider edge cases before diving into code. Practice writing regular expressions, but also understand manual parsing.

What are common mistakes when solving Valid Number?

Relying solely on regex without understanding the problem. Not handling edge cases like leading/trailing spaces.

#65

Valid Number

Hard

StringFinite State MachineRegular Expressions

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution involves parsing the string character by character while maintaining state variables to track the number format. This avoids the overhead of regex and allows for a single pass through the string.

⚙️

Algorithm

3 steps

1Step 1: Initialize flags for sign, digit, decimal point, and exponent.
2Step 2: Loop through each character in the string, updating flags based on the character type.
3Step 3: Ensure the final state is valid based on the flags set during the loop.

solution.py32 lines

1def is_valid_number(s):
2    has_digit = False
3    has_dot = False
4    has_e = False
5    n = len(s)
6    i = 0
7
8    if n == 0:
9        return False
10
11    if s[i] in ['+', '-']:
12        i += 1
13
14    while i < n:
15        if s[i].isdigit():
16            has_digit = True
17        elif s[i] == '.':
18            if has_dot or has_e:
19                return False
20            has_dot = True
21        elif s[i] in ['e', 'E']:
22            if has_e or not has_digit:
23                return False
24            has_e = True
25            has_digit = False
26            if i + 1 < n and s[i + 1] in ['+', '-']:
27                i += 1
28        else:
29            return False
30        i += 1
31
32    return has_digit

ℹ

Complexity note: The time complexity is O(n) because we make a single pass through the string, checking each character once. The space complexity is O(1) since we only use a few variables to track state.

1Understanding number formats is crucial.
2Regex can be powerful but may not be efficient.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.