The Weekly Challenge #295

Word Break • Jump Game
Official Challenge • My Solutions on GitHub

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 prefix s[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 substring s[j..i-1] exists in the dictionary set, then dp[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:

  1. We maintain two boundary markers:
    • farthest: The maximum index we can reach with the next jump.
    • current_end: The boundary of the current jump.
  2. 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: increment jumps and set current_end = farthest.
    • If current_end >= N - 1, we can reach or exceed the destination and return jumps immediately.
    • If at any point farthest <= i, we are stuck and cannot advance further, so we return -1.
  3. 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