Trie (Prefix Tree) Implementation

package Trie;
use strict;
use warnings;

sub new {
    my $class = shift;
    my $self = {
        children => {},
        is_end_of_word => 0
    };
    bless $self, $class;
    return $self;
}

sub insert {
    my ($self, $word) = @_;
    my $current = $self;
    
    for my $char (split //, lc($word)) {
        if (!exists $current->{children}->{$char}) {
            $current->{children}->{$char} = Trie->new();
        }
        $current = $current->{children}->{$char};
    }
    
    $current->{is_end_of_word} = 1;
}

sub search {
    my ($self, $word) = @_;
    my $current = $self;
    
    for my $char (split //, lc($word)) {
        if (!exists $current->{children}->{$char}) {
            return 0;
        }
        $current = $current->{children}->{$char};
    }
    
    return $current->{is_end_of_word};
}

sub starts_with {
    my ($self, $prefix) = @_;
    my $current = $self;
    
    for my $char (split //, lc($prefix)) {
        if (!exists $current->{children}->{$char}) {
            return 0;
        }
        $current = $current->{children}->{$char};
    }
    
    return 1;
}

sub get_words_with_prefix {
    my ($self, $prefix) = @_;
    my $current = $self;
    my @results = ();
    
    # Navigate to prefix node
    for my $char (split //, lc($prefix)) {
        if (!exists $current->{children}->{$char}) {
            return @results;
        }
        $current = $current->{children}->{$char};
    }
    
    # Collect all words from this point
    $self->_collect_words($current, $prefix, \@results);
    return @results;
}

sub _collect_words {
    my ($self, $node, $prefix, $results) = @_;
    
    if ($node->{is_end_of_word}) {
        push @$results, $prefix;
    }
    
    for my $char (keys %{$node->{children}}) {
        $self->_collect_words($node->{children}->{$char}, $prefix . $char, $results);
    }
}

# Example usage
package main;

my $trie = Trie->new();

# Insert words
my @words = qw(cat car card care careful carry case cast);
for my $word (@words) {
    $trie->insert($word);
}

print "Words inserted: " . join(", ", @words) . "\n";

# Search tests
my @search_tests = qw(car card careless);
for my $word (@search_tests) {
    my $found = $trie->search($word) ? "found" : "not found";
    print "Search '$word': $found\n";
}

# Prefix tests
my @prefix_tests = qw(car cas cat);
for my $prefix (@prefix_tests) {
    my $exists = $trie->starts_with($prefix) ? "exists" : "doesn't exist";
    print "Prefix '$prefix': $exists\n";
    
    my @words_with_prefix = $trie->get_words_with_prefix($prefix);
    if (@words_with_prefix) {
        print "  Words with prefix '$prefix': " . join(", ", @words_with_prefix) . "\n";
    }
}