Crate number_words 

Number Word Parser

This crate provides a solution to the number word problem, which involves parsing a string of digits into all possible corresponding words based on a given mapping (e.g., “1” -> ‘A’, “2” -> ‘B’, …, “26” -> ‘Z’).

It implements three different strategies to solve this problem, each with distinct performance characteristics and algorithmic approaches. This serves as a pedagogical example of optimization in Rust.

Strategies

1. Naive Recursion (NaiveParser): Directly constructs solutions using functional combinators. Simple to read but slow due to excessive allocation (VecDeque).
2. Depth-First Search (DfsParser): Uses a recursive backtracking approach with a single mutable buffer. Highly memory-efficient and fast for small to medium inputs.
3. Memoized Graph (MemoizedParser): A hybrid approach using Dynamic Programming. It precomputes the solution graph and solution counts to enable perfect pre-allocation and fast generation. Fastest for large, ambiguous inputs.

Structs

DfsParser

DFS Parser

MemoizedParser

Memoized Parser (Compiled Graph)

NaiveParser

Naive Parser

Enums

NumberWordsError

Errors that can occur during parsing.

Traits

NumberParser

A unified trait for all number parser implementations.

Functions

default_config

Generates the standard configuration mapping 1..26 to A..Z.

Type Aliases

Config

Configuration type representing the mapping from digit strings to characters. Example: vec![("1".to_string(), 'A'), ("2".to_string(), 'B'), ...]

Parser