Parsing Numbers and Strings

Algorithmic problems frequently require parsing integers in arbitrary radices (binary, octal, hexadecimal), indexing strings in $O(1)$ time, and converting between ASCII digits/letters and numeric indices (0..26).

Why Indexing `&str` Directly Is Forbidden in Rust:
  `&str` is UTF-8 (1 to 4 bytes per Unicode scalar `char` -> $O(n)$ `.chars().nth(i)`!)

Solution for $O(1)$ Indexing in Algorithmic String Problems:
  - ASCII strings:       `let bytes: &[u8] = s.as_bytes();`       (1 byte per char, $O(1)$ `bytes[i]`!)
  - Full Unicode chars:  `let chars: Vec<char> = s.chars().collect();` (4 bytes per char, $O(1)$ `chars[i]`!)

1. $O(1)$ String Indexing via .as_bytes() vs Vec<char>

Never call s.chars().nth(i) inside a loop! Because .chars().nth(i) walks UTF-8 bytes from the beginning of the string on every call, a loop for i in 0..n { let c = s.chars().nth(i); } turns an $O(n)$ algorithm into an $O(n^2)$ Time Limit Exceeded (TLE) bug!

2. Parsing Integers, Radices, and Byte Slices

pub fn parse_binary_and_hex() {
    // 1. Standard base-10 parsing via `.parse::<T>()` (`FromStr`):
    let decimal: i64 = "-9876543210".parse().unwrap();

    // 2. Parsing arbitrary bases (2..=36) via `from_str_radix`:
    let mask = u32::from_str_radix("1101_0110".replace('_', "").as_str(), 2).unwrap();
    let hex = u64::from_str_radix("deadbeef", 16).unwrap();

    // 3. Converting a single char to a digit in base `R` via `char::to_digit(radix)`:
    let digit_val: u32 = 'f'.to_digit(16).unwrap();
    assert_eq!(digit_val, 15);

    println!("decimal={decimal}, bin={mask:#010b}, hex={hex:#x}, 'f'={digit_val}");
}

/// Ultra-fast unsigned integer parser operating directly on raw ASCII `&[u8]` bytes:
#[inline]
pub fn parse_u64_bytes(bytes: &[u8]) -> u64 {
    bytes
        .iter()
        .fold(0u64, |acc, &b| acc * 10 + u64::from(b - b'0'))
}

/// Converts a lowercase ASCII word into 0..26 alphabet indices in O(n) time:
pub fn word_to_alpha_indices(word: &str) -> Vec<usize> {
    word.as_bytes()
        .iter()
        .map(|&b| (b - b'a') as usize)
        .collect()
}

fn main() {
    parse_binary_and_hex();

    let fast_num = parse_u64_bytes(b"18446744073709551615");
    assert_eq!(fast_num, u64::MAX);

    let indices = word_to_alpha_indices("rust");
    assert_eq!(indices, vec![17, 20, 18, 19]);
    println!("'rust' alphabet indices (0..26): {indices:?}");
}

decimal=-9876543210, bin=0b11010110, hex=0xdeadbeef, 'f'=15
'rust' alphabet indices (0..26): [17, 20, 18, 19]

3. Useful Split and Trim Methods for Structured Input Lines