Parse with a state machine

34 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Read the number out of the text -42abc: skip the spaces, notice the minus sign, read the digits 4 and 2, stop at the letter. By hand you do this without thinking. The trouble starts when you write it as code with a pile of if-statements: what if there are two signs, +-4? A sign after a digit, 4-2? Spaces after the sign? Digits so many that the number overflows a 32-bit integer? Each special case patches the last one, and a forgotten case gives a wrong answer silently. Testing every combination of quirks by hand is slow and never feels finished.

Build the structure, one piece at a time

The structure is a state machine: a short list of states you can be in, and for each state a rule for what each kind of character does. The whole parse is one left-to-right pass, and the only memory is the current state plus the value built so far.

1. State SPACE: a space keeps you here; a sign moves you to SIGN and records it; a digit moves you to DIGITS; anything else ends.
2. State SIGN: a digit moves you to DIGITS; anything else, including another sign or a space, ends with value 0.
3. State DIGITS: a digit is appended, value = value·10 + digit; anything else ends.
4. State END: nothing more is read.

Run -42abc through it:

Apply the sign: −42. The last piece is the overflow guard inside DIGITS: before value·10 + digit, check whether value is already above (limit − digit)/10; if so, clamp to the limit and end. For 32-bit integers the limits are 2³¹ − 1 = 2,147,483,647 and −2³¹.

Why it is correct

The invariant: the current state and value together describe exactly the valid prefix read so far. In SPACE nothing has been read; in SIGN a sign has been consumed and no digit yet; in DIGITS the value equals the digits read so far, as a number. Each rule consumes one character and moves to the state that describes the new prefix, and every character falls under exactly one rule, so there is no input the machine does not know what to do with. "Two signs" cannot happen because SIGN has no rule that accepts a sign; it ends instead. That is the whole point: the quirks are not patches, they are the absence of an arrow.

value_new = value·10 + d, allowed only if value ≤ (L − d) / 10

Why it is fast

One character is read per step, each step does a constant amount of work (a few comparisons and one multiply-add), and nothing is ever re-read. So parsing n characters is O(n) with O(1) memory. The overflow check is a comparison per digit, so it adds nothing to the order. A regular expression does the same work in principle, but hides the overflow rule and the clamping, which the state machine makes explicit.

How to recognise it in an interview

Cues: "parse", "convert the string to", a format with optional parts in a fixed order (sign, digits, dot, exponent), "stop at the first invalid character", roman numerals, version strings. Say: I will list the states and draw the arrows before writing any code, then every character falls into exactly one case. String to Integer (atoi) is the example. Roman to Integer is a two-state machine: compare each symbol with the next and subtract or add. Fraction to Recurring Decimal is a state machine over remainders: the state is the remainder, and a repeated remainder means the digits repeat from there.

02The idea in one line

Walk characters once with explicit states: sign, digits, overflow guard.

Reach for it when: atoi, valid number, roman numerals, version compare, fraction to decimal.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: atoi on ' -42abc'. These are its captions in order, so you can follow without the video or check a step you missed.

1. Explicit states: skip spaces, read one sign, then digits, then stop
2. SPACE: skip leading blanks
3. SIGN: '-' sets sign = −, allowed only once
4. DIGITS: value = value·10 + 4 = 4 (overflow check first)
5. DIGITS: value = value·10 + 2 = 42 (overflow check first)
6. 'a' is not a digit: END, everything after is ignored
7. Apply the sign: -42, clamped to the 32-bit range if needed
8. One pass over the characters: O(n), no regex, no surprises

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in String Algorithms: KMP failure function, Rolling hash (Rabin–Karp), Reverse-and-build string transforms, Merge / compare two strings in lockstep, Multi-pattern scan with a set of lengths.