The weekly challenge 295 - Task 1: Word Break

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-295/#TASK1
 3 #
 4 # Task 1: Word Break
 5 # ==================
 6 #
 7 # You are given a string, $str, and list of words, @words.
 8 #
 9 # Write a script to return true or false whether the given string can be
10 # segmented into a space separated sequence of one or more words from the given
11 # list.
12 #
13 ## Example 1
14 ##
15 ## Input: $str = 'weeklychallenge', @words = ("challenge", "weekly")
16 ## Output: true
17 #
18 ## Example 2
19 ##
20 ## Input: $str = "perlrakuperl", @words = ("raku", "perl")
21 ## Output: true
22 #
23 ## Example 3
24 ##
25 ## Input: $str = "sonsanddaughters", @words = ("sons", "sand", "daughters")
26 ## Output: false
27 #
28 ############################################################
29 ##
30 ## discussion
31 ##
32 ############################################################
33 #
34 # For each word in the array, we check if it is at the beginning of $str.
35 # If so, we remove that part from $str and run the function recursively.
36 # If we have a case where the whole $str is one of the words, we return true.
37 # If we end up with an empty $str, we return false.
38 
39 use strict;
40 use warnings;
41 
42 word_break('weeklychallenge', "challenge", "weekly");
43 word_break("perlrakuperl", "raku", "perl");
44 word_break("sonsanddaughters", "sons", "sand", "daughters");
45 
46 sub word_break {
47    my ($str, @words) = @_;
48    print "Input: $str, (" . join(", ", @words) . ")\n";
49    if(word_break_($str, @words)) {
50       print "Output: true\n";
51    } else {
52       print "Output: false\n";
53    }
54 }
55 
56 sub word_break_ {
57    my ($str, @words) = @_;
58    my $result = 0;
59    foreach my $word (@words) {
60       return 1 if $word eq $str;
61       if(substr($str, 0, length($word)) eq $word) {
62          $result = word_break_(substr($str,length($word)), @words);
63       }
64       last if $result;
65    }
66    return $result;
67 }