Challenge 099

TASK #1 › Pattern Match

Task

You are given a string $S and a pattern $P.

Write a script to check if given pattern validate the entire string. Print 1 if pass otherwise 0.

The patterns can also have the following characters:

• ? - Match any single character.
• * - Match any sequence of characters.

My solution

This seems pretty straight forward. I take the pattern, escape the meta characters, except ? and *, replace the ? with . and * with .+, anchor the regexp to the entire string, and then test the match.

The only question is does 'any sequence of characters' include a sequence of 0 characters? I assumed it doesn't, but if it did, replace .+ with .*.

Examples

» ./ch-1.pl abcde "a*e"
1

» ./ch-1.pl abcde "a*d"
0

» ./ch-1.pl abcde "?b*d"
0

» ./ch-1.pl abcde "a*c?e"
1

TASK #2 › Unique Subsequence

Task

You are given two strings $S and $T.

Write a script to find out count of different unique subsequences matching $T without changing the position of characters.

My solution

For this task I used a recursive subroutine called _find_string. It starts with the two input vales, and works through each character in $S until the first character is found. When this occurs, I call the function again with $S now the remainder of the string, and the first character of $T removed. Once we get to the end ($T is the last character) we add 1 to the $matches variable.

I'm not sure a recursive function is the best way to complete the task, but it works. If performance was an issue, we could always reduce $S to only contain the characters in $T, something like: $S =~ s/[^$T]//g; and escaping the meta characters as needed.

Examples

» ./ch-2.pl littleit lit
5

» ./ch-2.pl london lon
3