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