Parsing and simulation

Big idea

Parsing problems have no clever trick: move one index through the string and handle each kind of character in a fixed order — whitespace, sign, digits, separators. The difficulty is the edge cases, so write them down before you code and test each one.

The index-walking skeleton

i, n = 0, len(s)
while i < n and s[i] == ' ':      # 1. skip what you ignore
    i += 1
if i < n and s[i] in '+-':        # 2. read optional markers
    ...
while i < n and s[i].isdigit():   # 3. read the main run
    ...
# 4. stop at the first character that doesn't fit

Always check i < n before reading s[i]. Most parsing bugs are reading one past the end.

String to integer (atoi)

Rules: skip leading spaces, read an optional sign, read digits until a non-digit, clamp to the 32-bit range [−2³¹, 2³¹ − 1].

def my_atoi(s):
    INT_MAX, INT_MIN = 2**31 - 1, -2**31
    i, n = 0, len(s)
    while i < n and s[i] == ' ':
        i += 1
    sign = 1
    if i < n and s[i] in '+-':
        sign = -1 if s[i] == '-' else 1
        i += 1
    num = 0
    while i < n and s[i].isdigit():
        num = num * 10 + (ord(s[i]) - ord('0'))
        if sign * num > INT_MAX: return INT_MAX
        if sign * num < INT_MIN: return INT_MIN
        i += 1
    return sign * num

num = num * 10 + digit is how every number parser builds a value left to right. In Java or C++, check for overflow before multiplying: num > (INT_MAX - digit) / 10.

Edge cases worth testing: "", " ", "+", "-0", " -42abc", "2147483648", "--5".

Thinking of it as states also cracks harder validators like "Valid Number" (signs, decimals, exponents): list the states, list which character moves you where, reject anything else.

Watch it

Trace the atoi walk on a short input.

Splitting into parts

Compare version numbers "1.01" and "1.001.0": split on dots, compare part by part as integers, and treat a missing part as 0.

def compare_version(a, b):
    pa, pb = a.split('.'), b.split('.')
    for k in range(max(len(pa), len(pb))):
        x = int(pa[k]) if k < len(pa) else 0
        y = int(pb[k]) if k < len(pb) else 0
        if x != y:
            return 1 if x > y else -1
    return 0

Run-length style walks

String Compression turns "aaabcc" into "a3bc2". Walk with two indices: i marks the start of a run, j advances while s[j] == s[i]; the run length is j - i; then set i = j.

def compress(s):
    out, i = [], 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
            j += 1
        out.append(s[i] + (str(j - i) if j - i > 1 else ""))
        i = j
    return "".join(out)

The inner loop looks nested but every character is visited once overall: O(n). The same run-walking reads "Count and Say" sequences.

A checklist before you submit

• Empty string, all spaces, a single character.
• Leading and trailing separators (".1.", " hello ").
• Signs without digits, digits without signs.
• Numbers at and just past the integer limits.
• Mixed case, if the problem cares about letters.

Practice

• String to Integer (atoi)
• Compare Version Numbers
• String Compression
• Count and Say
• Zigzag Conversion
• Valid Number — the state-machine approach.
• Encode and Decode Strings — length-prefix each word so any character is safe.
• Text Justification

Quick check