Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 225 ยท Strings

String Parsing Problems: atoi, IP Validation, Big Multiplication and Isomorphic Strings

Solve implementation-heavy string problems in Python: a safe atoi with overflow clamping, IPv4 and IPv6 validation, multiplying huge numbers as strings and isomorphic strings.

Some string problems have no clever algorithm at all. They are hard because of edge cases: leading spaces, signs, overflow, empty parts, leading zeros. Interviewers like them because they test whether you read the specification carefully and write code that does not break on odd input.

In this lesson you will write a robust atoi (string to integer), validate IPv4 and IPv6 addresses, multiply two huge numbers given as strings, and test whether two strings are isomorphic. The approach is always the same: state the rules in a short list, handle one rule at a time, and test the weird cases first. Review String Basics and String Problems if you need a refresher on slicing and character handling. (Roman numerals and interleaving strings have their own lessons: compression and encoding and string DP.)

atoi: string to integer

Python's int() is too forgiving or too strict for this exercise, so we implement the classic C-style rules:

  1. Skip leading spaces.
  2. Read an optional + or -.
  3. Read digits until the first non-digit; ignore the rest.
  4. If there are no digits, the result is 0.
  5. Clamp the result to the 32-bit signed range [-2**31, 2**31 - 1].

In a language with fixed-width integers you must check for overflow before each multiply. Python integers never overflow, so we clamp at the end (or early, to stop long loops).

Python A careful atoi

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Note the character test "0" <= s[i] <= "9". Do not use s[i].isdigit() here: it accepts other Unicode digits (such as Arabic-Indic digits) that ord(s[i]) - ord("0") would convert wrongly.

Validate an IP address

IPv4 has four decimal parts separated by dots. Each part is a number from 0 to 255 with no leading zeros (except the single digit 0 itself) and no sign or spaces. IPv6 has eight groups of one to four hexadecimal digits separated by colons.

The structure of a good solution: split on the separator, check the number of parts, then validate each part with a small function.

Python IPv4 and IPv6 validators

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Real IPv6 allows :: to compress zeros; the version above covers only the full form. In real code use the ipaddress module (ipaddress.ip_address(s)), but know how to write the parser by hand.

Multiply two numbers given as strings

If the numbers are too big for any integer type (in other languages), you multiply them like you did in school, digit by digit. The key observation: the product of digits a[i] and b[j] contributes to the result at positions i + j and i + j + 1 (counting from the left in a result array of length len(a) + len(b)).

  1. Make a result array res of zeros with length m + n.
  2. For i from right to left in a, for j from right to left in b: add a[i] * b[j] to res[i + j + 1], then carry the part above 9 into res[i + j].
  3. Strip leading zeros.
Python Multiply strings, then check against int

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time is O(m * n), space O(m + n). Faster methods (Karatsuba, FFT) are covered in FFT and polynomials.

Isomorphic strings

Two strings s and t of equal length are isomorphic if you can replace the characters of s one-to-one to get t. "One-to-one" is the key: two different characters of s cannot map to the same character of t, and one character cannot map to two. egg and add are isomorphic; foo and bar are not (o would map to both a and r); badc and baba are not (b and d would both map to b).

Keep two dictionaries, one for each direction, and check both on every position. The same idea solves "word pattern" (does a text follow a pattern like abba?).

Python Isomorphic strings and word pattern

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A shortcut: map each string to a "first occurrence" signature (egg becomes [0, 1, 1], add becomes [0, 1, 1]) and compare the signatures. That is the idea behind canonical keys in hashing patterns.

Common mistakes

  • Using isdigit() for ASCII digit checks. It accepts non-ASCII digits and some superscripts.
  • Allowing leading zeros in IPv4 parts such as 01.
  • Checking only one direction of the isomorphism mapping.
  • Forgetting that "-0" and "+0" are valid input for atoi and should give 0.
  • Leaving leading zeros in the product of two strings.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does my_atoi(' -42abc') return under the C-style rules?

    Leading spaces are skipped, the minus sign is read, digits are read until the first non-digit, and the rest is ignored.
  2. 2. Which of these is NOT a valid IPv4 address?

    A part such as 01 has a leading zero, which is not allowed.
  3. 3. When multiplying digit strings a (length m) and b (length n), where does a[i] * b[j] contribute first?

    The low digit of the partial product goes to position i + j + 1; the carry goes to i + j.
  4. 4. Why do we need two dictionaries to test isomorphic strings?

    With only a forward map, 'badc' and 'baba' would pass even though b and d would both map to b.

Summary

  • Write the rules as a numbered list first; most parsing bugs come from forgotten rules.
  • atoi: skip spaces, read an optional sign, read digits, clamp to the 32-bit range.
  • IPv4 parts are 0 to 255 with no leading zeros; IPv6 has eight groups of 1 to 4 hex digits (in the full form).
  • School multiplication on digit arrays works in O(m * n); the digit pair (i, j) lands at i + j + 1.
  • Isomorphic strings need a one-to-one mapping, so check both directions.

Next: Alien Dictionary and Lexicographic Rank, where strings are ordered by unusual rules.