The Weekly Challenge 299

Replace Words & Word Search

Solutions on GitHub

Task 1: Replace Words

You are given an array of words and a sentence. Write a script to replace each word in the sentence with the shortest prefix that matches a dictionary word (if any).

Example Output

Input: @words = ("cat", "bat", "rat"), $sentence = "the cattle was rattle by the battery" Output: "the cat was rat by the bat" Input: @words = ("a", "b", "c"), $sentence = "aab aac and cac bab" Output: "a a a c b" Input: @words = ("man", "bike"), $sentence = "the manager was hit by a biker" Output: "the man was hit by a bike"

Logic

First, sort the dictionary of root words by ascending length so that the shortest match is always tested first. For each token in the sentence, iterate over the sorted dictionary; if the token starts with a root word (using index($token, $root) == 0 in Perl or token.startswith(root) in Python), replace the token with that root and stop searching. Finally, join the tokens back with single spaces.

Perl Solution

ch-1.pl

sub replace_words ($words, $sentence) { ( $words, $sentence ) = $ARGS_CHECK->( $words, $sentence ); my @dict = sort { length($a) <=> length($b) } @$words; my @out; for my $token ( split /\s+/, $sentence ) { my $replacement = $token; for my $root (@dict) { if ( index( $token, $root ) == 0 ) { $replacement = $root; last; } } push @out, $replacement; } return join ' ', @out; }

Python Solution

ch-1.py

def replace_words(words: Sequence[str], sentence: str) -> str: roots = sorted(words, key=len) out: list[str] = [] for token in sentence.split(): replacement = token for root in roots: if token.startswith(root): replacement = root break out.append(replacement) return " ".join(out)

Task 2: Word Search

You are given a 2D grid of characters and a target word string. Determine if the word exists in the grid along an orthogonal path (horizontal or vertical adjacent cells) without visiting any cell more than once per word path.

Example Output

Grid: [ [A, B, D, E], [C, B, C, A], [B, A, A, D], [D, B, B, C] ] Input: $str = "BDCA" Output: true Input: $str = "ABAC" Output: false Input: $str = "CCCAA" Output: true

Logic

We use depth-first search (DFS) with backtracking. For each starting cell (r, c) matching the first letter of the target word, we explore 4 orthogonal directions (up, down, left, right). We track visited cells with a 2D boolean array to prevent re-using cells, and backtrack upon returning. If all characters match sequentially, return true.

Perl Solution

ch-2.pl

sub word_search ($grid, $str) { ( $grid, $str ) = $ARGS_CHECK->( $grid, $str ); return 1 if $str eq ''; my $rows = scalar @$grid; my $cols = scalar @{ $grid->[0] }; die 'Non-rectangular grid' if grep { @$_ != $cols } @$grid; my @chars = split //, $str; my @visited = map { [ (0) x $cols ] } 1 .. $rows; my $dfs; $dfs = sub ( $r, $c, $idx ) { return 1 if $idx == @chars; return 0 if $r < 0 || $r >= $rows || $c < 0 || $c >= $cols; return 0 if $visited[$r][$c]; return 0 if $grid->[$r][$c] ne $chars[$idx]; $visited[$r][$c] = 1; my $ok = $dfs->( $r + 1, $c, $idx + 1 ) || $dfs->( $r - 1, $c, $idx + 1 ) || $dfs->( $r, $c + 1, $idx + 1 ) || $dfs->( $r, $c - 1, $idx + 1 ); $visited[$r][$c] = 0; return $ok; }; for my $r ( 0 .. $rows - 1 ) { for my $c ( 0 .. $cols - 1 ) { return 1 if $dfs->( $r, $c, 0 ); } } return 0; }

Python Solution

ch-2.py

def word_search(grid: Grid, text: str) -> bool: if not text: return True rows = len(grid) cols = len(grid[0]) if any(len(row) != cols for row in grid): raise ValueError("Non-rectangular grid") visited = [[False] * cols for _ in range(rows)] def dfs(r: int, c: int, idx: int) -> bool: if idx == len(text): return True if r < 0 or r >= rows or c < 0 or c >= cols: return False if visited[r][c]: return False if grid[r][c] != text[idx]: return False visited[r][c] = True ok = ( dfs(r + 1, c, idx + 1) or dfs(r - 1, c, idx + 1) or dfs(r, c + 1, idx + 1) or dfs(r, c - 1, idx + 1) ) visited[r][c] = False return ok for r in range(rows): for c in range(cols): if dfs(r, c, 0): return True return False