Task — Completing word

You are given a string $str containing alphnumeric characters, and an array of strings containing only alphabetic characters, @str.

Write a script to find the shortest completing word. If none is found return an empty string.

A completing word is a word that contains all the letters in the given string, ignoring spaces and numbers. If a letter appears more than once in the given string then it must appear the same number or more times in the word.

Examples

Example 1
Input: $str = 'aBc 11c'
       @str = ('accbbb', 'abc', 'abbc')
Output: 'accbbb'

The given string contains following, ignoring case and 
number:
a 1 times
b 1 times
c 2 times

The only string in the given array that satisfies the 
condition is 'accbbb'.

Example 2
Input: $str = 'Da2 abc'
       @str = ('abcm', 'baacd', 'abaadc')
Output: 'baacd'

The given string contains following, ignoring case and 
number:
a 2 times
b 1 times
c 1 times
d 1 times

The are 2 strings in the given array that satisfies 
the condition:
'baacd' and 'abaadc'.

Shortest of the two is 'baacd'

Example 3
Input: $str = 'JB 007'
       @str = ('jj', 'bb', 'bjb')
Output: 'bjb'

The given string contains following, ignoring case and 
number:
j 1 times
b 1 times

The only string in the given array that satisfies the 
condition is 'bjb'.

Analysis

My solution to this is based on the following strategy:

• Create a regular expresion from $str that can be used to distinguish between valid and invalid members of @str.
• Transform each member of @str into a form that can be matched against the regex.

The regex comprises all the letters in $str, lower cased, sorted, and separated with '.*'. So, for example, 'house' becomes 'e.*h.*o.*s.*u.*'.

Each element of @str is then lower-cased and sorted. Any that match the regex are completing words as defined, and all that remains is to identify the shortest (of which there may be more than one).

Try it 

Script

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2024-04-15
use utf8;     # Week 265 - task 2 - Completing word
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

completing_word('aBc 11c', ['accbbb', 'abc', 'abbc']);
completing_word('Da2 abc', ['abcm', 'baacd', 'abaadc']);
completing_word('JB 007', ['jj', 'bb', 'bjb']);
completing_word('P A R A M O U N T', ['tnoumarap', 'aamnoprtu']);
completing_word('xxAAxx', ['xxAxx', 'xxAAxx', 'xxAAAxx']);
completing_word('zz', [qw[the weekly challenge is a puzzle]]);

sub completing_word {
    
    my ($str, @str, $s, $ss, $result, $shortest, $l);
    
    # initialise
    $str = $_[0];
    @str = @{$_[1]};
    say qq[\nInput:  \$str = '$str', \@str = ('] . join(q[', '], @str) . q[')];
    
    # create a regex match like a.*b.*c.* from the sorted alpha chars in $str
    $str =~ s|[^a-z]||gi;
    $str = join('', sort {$a cmp $b} split('', lc($str)));
    $str =~ s|(.)|$1.*|g;
    
    # loop over @str to find best match
    $shortest = 999;
    $result = q['', ];
    for $s (@str) {
        
        # sort and lower case the letters of $str[$i] and see if they match the regex
        $ss = join('', sort {$a cmp $b} split('', lc($s)));
        next unless $ss =~ m|$str|;
        
        # see if this is the shortest or equal shortest match
        $l = length($s);
        if ($l < $shortest) {
            $result = qq['$s', ];
            $shortest = $l;
        } elsif ($l == $shortest) {
            $result .= qq['$s', ];
        }       
    }
    
    # and output the results
    say qq[Output: ] . substr($result, 0, -2);
}

Output

Input:  $str = 'aBc 11c', @str = ('accbbb', 'abc', 'abbc')
Output: 'accbbb'

Input:  $str = 'Da2 abc', @str = ('abcm', 'baacd', 'abaadc')
Output: 'baacd'

Input:  $str = 'JB 007', @str = ('jj', 'bb', 'bjb')
Output: 'bjb'

Input:  $str = 'P A R A M O U N T', @str = ('tnoumarap', 'aamnoprtu')
Output: 'tnoumarap', 'aamnoprtu'

Input:  $str = 'xxAAxx', @str = ('xxAxx', 'xxAAxx', 'xxAAAxx')
Output: 'xxAAxx'

Input:  $str = 'zz', @str = ('the', 'weekly', 'challenge', 'is', 'a', 'puzzle')
Output: 'puzzle'