LeetCode Solution 65 - Valid Number

 Problem Statement

The problem "Valid Number" (LeetCode #65) asks us to determine if a given string represents a valid number. A valid number can be an integer, a decimal, or a number with an exponent. The input string may contain digits (0-9), a decimal point (.), an exponent (e or E), and sign characters (+ or -). Spaces are not allowed.

Constraints:

• The input is a non-empty string.
• The string may contain at most one decimal point.
• The string may contain at most one exponent ('e' or 'E'), which must be followed by an integer.
• Leading and trailing spaces are not valid.
• Signs (+ or -) are only allowed at the beginning or right after an exponent.

Optimal Approach: Finite State Machine (FSM)

The best approach is to use a finite state machine (FSM) that validates transitions between different states.

Key Observations:

1. A number can be an integer or a floating point number.
2. An exponent (e or E) must be followed by an integer.
3. Signs (+ or -) must be at the beginning or immediately after e/E.
4. A decimal point (.) can only appear once and must be followed by at least one digit (unless there's an exponent).
5. Any character other than 0-9, e/E, +/-, and . makes the number invalid.

Implementation Steps:

1. Use flags to track if a decimal point, exponent, or digit has been encountered.
2. Process the string character by character, ensuring valid transitions.
3. Return true only if the last encountered character is valid.

---

LeetCode-Compatible C++ Solution

Below is a directly submittable C++ solution using a finite state machine (FSM) approach.

class Solution {
public:
    bool isNumber(string s) {
        int n = s.length();
        bool seenDigit = false, seenDot = false, seenExponent = false;
        
        for (int i = 0; i < n; i++) {
            if (isdigit(s[i])) {
                seenDigit = true; // Digits are always valid
            }
            else if (s[i] == '+' || s[i] == '-') {
                if (i > 0 && (s[i - 1] != 'e' && s[i - 1] != 'E'))
                    return false; // Sign can only appear at start or after 'e/E'
            }
            else if (s[i] == '.') {
                if (seenDot || seenExponent) return false; // Only one dot before exponent
                seenDot = true;
            }
            else if (s[i] == 'e' || s[i] == 'E') {
                if (seenExponent || !seenDigit) return false; // Must have a digit before 'e/E'
                seenExponent = true;
                seenDigit = false; // Reset to check for digits after 'e/E'
            }
            else {
                return false; // Invalid character
            }
        }
        return seenDigit; // Must end with a digit
    }
};

---

Step-by-Step Explanation of Code

1. Initialize flags:

   • seenDigit = false → Ensures at least one digit is encountered.
   • seenDot = false → Ensures only one . is present.
   • seenExponent = false → Ensures only one e/E is present.

2. Iterate through the string:

   • If it's a digit (0-9), mark seenDigit = true.
   • If it's a sign (+/-), ensure it appears at the start or immediately after 'e/E'.
   • If it's a dot (.), ensure it hasn't already appeared and isn't after 'e/E'.
   • If it's an exponent (e/E), ensure there's at least one digit before and it's the first occurrence.
   • Any other character is invalid.

3. Final check:

   • The string must end with a valid digit to be considered a valid number.

---

Dry Run / Execution Steps

Input	Processing Steps	Output
"2"	Digit encountered → Valid	✅ True
"0.1"	0 → . → 1 (valid float)	✅ True
"abc"	Invalid character a	❌ False
"1e10"	1 → e → 10	✅ True
"1e"	1 → e (no digits after)	❌ False
".1"	. → 1 (valid)	✅ True
"1..1"	Multiple .	❌ False

---

Alternative Approaches & Their Drawbacks

Approach	Time Complexity	Space Complexity	Why Not Optimal?
Brute Force	O(N)	O(1)	Hard to implement and error-prone
Regular Expressions	O(N)	O(1)	Less readable, complex patterns
FSM (Best)	O(N)	O(1)	Efficient and structured

---

Complexity Analysis

• Time Complexity: O(N), since we iterate through the string once.
• Space Complexity: O(1), since we only use a few boolean variables.

---

Conclusion

The finite state machine (FSM) approach is the best solution due to its clarity, efficiency, and direct validation of character sequences. We covered multiple edge cases, alternative methods, and a step-by-step breakdown of the problem.

Similar Problems for Practice:

1. String to Integer (atoi) - LeetCode #8
2. Basic Calculator - LeetCode #224
3. Valid Palindrome - LeetCode #125