The weekly challenge 352 - Task 1: Match String

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-352/#TASK1
 3 #
 4 # Task 1: Match String
 5 # ====================
 6 #
 7 # You are given an array of strings.
 8 #
 9 # Write a script to return all strings that are a substring of another word in
10 # the given array in the order they occur.
11 #
12 ## Example 1
13 ##
14 ## Input: @words = ("cat", "cats", "dog", "dogcat", "dogcat", "rat", "ratcatdogcat")
15 ## Output: ("cat", "dog", "dogcat", "rat")
16 #
17 #
18 ## Example 2
19 ##
20 ## Input: @words = ("hello", "hell", "world", "wor", "ellow", "elloworld")
21 ## Output: ("hell", "world", "wor", "ellow")
22 #
23 #
24 ## Example 3
25 ##
26 ## Input: @words = ("a", "aa", "aaa", "aaaa")
27 ## Output: ("a", "aa", "aaa")
28 #
29 #
30 ## Example 4
31 ##
32 ## Input: @words = ("flower", "flow", "flight", "fl", "fli", "ig", "ght")
33 ## Output: ("flow", "fl", "fli", "ig", "ght")
34 #
35 #
36 ## Example 5
37 ##
38 ## Input: @words = ("car", "carpet", "carpenter", "pet", "enter", "pen", "pent")
39 ## Output: ("car", "pet", "enter", "pen", "pent")
40 #
41 ############################################################
42 ##
43 ## discussion
44 ##
45 ############################################################
46 #
47 # We check each element in the list against each other element in the list.
48 # If it's a substring of the other word, we keep it and stop checking it
49 # against other words in the list. In order to avoid duplicates, we keep
50 # track of all the words we already saw and skip checking if we saw the word
51 # already earlier.
52 
53 use v5.36;
54 match_string("cat", "cats", "dog", "dogcat", "dogcat", "rat", "ratcatdogcat");
55 match_string("hello", "hell", "world", "wor", "ellow", "elloworld");
56 match_string("a", "aa", "aaa", "aaaa");
57 match_string("flower", "flow", "flight", "fl", "fli", "ig", "ght");
58 match_string("car", "carpet", "carpenter", "pet", "enter", "pen", "pent");
59 
60 sub match_string (@words) {
61     say "Input: (\"" . join("\", \"", @words) . "\")";
62     my @output = ();
63     my $seen = {};
64     OUTER: foreach my $i (0..$#words) {
65         next if $seen->{$words[$i]};
66         foreach my $j (0..$#words) {
67             next if $i == $j;
68             if($words[$j] =~ m/$words[$i]/) {
69                 push @output, $words[$i];
70                 $seen->{$words[$i]} = 1;
71                 next OUTER;
72             }
73         }
74     }
75     say "Output: (\"" . join("\", \"", @output) . "\")";
76 }
77