leetcode/strings/0065-valid-number.py at main · shahzodshafizod/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import unittest

# https://leetcode.com/problems/valid-number/

# python3 -m unittest strings/0065-valid-number.py


class Solution(unittest.TestCase):
    # # Approach #1: Brute Force - Try/Except parsing
    # # Try to convert string to float and catch exceptions
    # # Time: O(N) - parsing the string
    # # Space: O(1) - no extra space
    # def isNumber(self, s: str) -> bool:
    #     try:
    #         float(s)
    #         return True
    #     except ValueError:
    #         return False
    # # Note: This doesn't work because Python's float() is more permissive
    # # than the problem requirements (e.g., accepts "inf", "nan")

    # Approach #2: Optimized - State Machine / Character-by-character parsing
    # Parse string while tracking: signs, digits, decimal point, exponent
    # Valid number = (integer OR decimal) + optional exponent
    # Time: O(N) - single pass through string
    # Space: O(1) - only boolean flags
    def isNumber(self, s: str) -> bool:
        seen_digit = False
        seen_exponent = False
        seen_dot = False

        for i, char in enumerate(s):
            if char.isdigit():
                seen_digit = True
            elif char in ['+', '-']:
                # Sign is valid at start OR right after 'e'/'E'
                if i > 0 and s[i - 1] not in ['e', 'E']:
                    return False
            elif char == '.':
                # Dot is invalid after exponent or another dot
                if seen_exponent or seen_dot:
                    return False
                seen_dot = True
            elif char in ['e', 'E']:
                # Exponent requires at least one digit before it
                # and cannot appear twice
                if seen_exponent or not seen_digit:
                    return False
                seen_exponent = True
                seen_digit = False  # Must have digit after exponent
            else:
                # Invalid character
                return False

        return seen_digit

    def test(self):
        for s, expected in [
            # Valid numbers
            ("0", True),
            ("2", True),
            ("0089", True),
            ("-0.1", True),
            ("+3.14", True),
            ("4.", True),
            ("-.9", True),
            ("2e10", True),
            ("-90E3", True),
            ("3e+7", True),
            ("+6e-1", True),
            ("53.5e93", True),
            ("-123.456e789", True),
            # Invalid numbers
            ("abc", False),
            ("1a", False),
            ("1e", False),
            ("e3", False),
            ("99e2.5", False),
            ("--6", False),
            ("-+3", False),
            ("95a54e53", False),
            ("e", False),
            (".", False),
            ("+", False),
            ("6e6.5", False),
            (".e1", False),
            ("3.", True),
            (".1", True),
        ]:
            output = self.isNumber(s)
            self.assertEqual(expected, output, f"expected: {expected}, output: {output}")