Task 1: Word Break
You are given a string and a list of words. Write a script to determine if the string can be segmented into a space-separated sequence of one or more words from the dictionary. Return 'true' if it can be segmented, 'false' otherwise.
Method Explanation
This is the classic Word Break problem, efficiently solved using Dynamic Programming:
- Let
dp[i]be a boolean flag indicating whether the prefixs[0..i-1]can be segmented into words from the dictionary. - Base case:
dp[0] = true(an empty string can always be formed with zero words). - For each index $i$ from 1 to $N$:
- Iterate over every split point $j$ from 0 to $i - 1$.
- If
dp[j]is true and the substrings[j..i-1]exists in the dictionary set, thendp[i]is true and we can break early to test the next prefix.
- The final answer is whether
dp[N]is true.
Perl Implementation
sub word_break ( $str, $words ) {
( $str, $words ) = $WORD_BREAK_CHECK->( $str, $words );
my %word_set = map { $_ => 1 } @$words;
my $length = length($str);
my @dp = (0) x ( $length + 1 );
$dp[0] = 1;
for my $i ( 1 .. $length ) {
for my $j ( 0 .. $i - 1 ) {
if ( $dp[$j] && exists $word_set{ substr( $str, $j, $i - $j ) } ) {
$dp[$i] = 1;
last;
}
}
}
return $dp[$length] ? 'true' : 'false';
}
Python Implementation
def word_break(s: str, words: Sequence[str]) -> str:
"""Determine if string s can be segmented into words from given sequence."""
word_set = set(words)
length = len(s)
dp = [False] * (length + 1)
dp[0] = True
for i in range(1, length + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return "true" if dp[length] else "false"
Task 2: Jump Game
You are given an array of integers where each element represents your maximum jump length from that position. Write a script to return the minimum number of jumps to reach the last index. If you cannot reach the last index, return -1.
Method Explanation
We can solve Jump Game II / minimum jumps in linear time $O(N)$ using a Greedy algorithm:
- We maintain two boundary markers:
farthest: The maximum index we can reach with the next jump.current_end: The boundary of the current jump.
- As we iterate from index 0 up to $N - 2$:
- We update
farthest = max(farthest, i + nums[i]). - When we reach
i == current_end, we must make a jump: incrementjumpsand setcurrent_end = farthest. - If
current_end >= N - 1, we can reach or exceed the destination and returnjumpsimmediately. - If at any point
farthest <= i, we are stuck and cannot advance further, so we return-1.
- We update
- If the loop completes without reaching the end, return
-1.
Perl Implementation
sub min_jumps ($ints) {
($ints) = $INTS_CHECK->($ints);
my $n = scalar @$ints;
return 0 if $n <= 1;
return -1 if $ints->[0] == 0;
my $jumps = 0;
my $current_end = 0;
my $farthest = 0;
for my $i ( 0 .. $n - 2 ) {
$farthest = max( $farthest, $i + $ints->[$i] );
if ( $i == $current_end ) {
$jumps++;
$current_end = $farthest;
return $jumps if $current_end >= $n - 1;
}
return -1 if $farthest <= $i;
}
return -1;
}
Python Implementation
def min_jumps(ints: Sequence[int]) -> int:
"""Calculate the minimum number of jumps to reach the last index."""
n = len(ints)
if n <= 1:
return 0
if ints[0] == 0:
return -1
jumps = 0
current_end = 0
farthest = 0
for i in range(n - 1):
farthest = max(farthest, i + ints[i])
if i == current_end:
jumps += 1
current_end = farthest
if current_end >= n - 1:
return jumps
if farthest <= i:
return -1
return -1