Pseudo Test | GrassHoppers

Pseudocode Challenge

Challenge: Challenge: Word Segmentation with Minimum Dictionary Lookups

Problem Statement:

You are given a string S of length n, consisting of only lowercase English letters, and a dictionary D of valid English words. The task is to segment the string S into a sequence of words that minimizes the number of dictionary lookups.

For each lookup in the dictionary, you incur a "cost" of 1, regardless of whether the word exists in the dictionary or not.

Objective: Write a pseudocode algorithm to split the string S into a sequence of words from the dictionary such that the number of dictionary lookups is minimized. If the string cannot be segmented into valid words, return -1.

Constraints:

The dictionary lookup function, isWord(word), returns True if word is in the dictionary and False otherwise.
String S has a maximum length of 1000 characters.
The dictionary D contains at most 10,000 words.

Write your pseudocode below

Feedback on your code

Correct Code

function minDictionaryLookups(S, D):
# Memoization array for storing results of subproblems
memo = array of size len(S) filled with -1

function minLookups(S, index):
# Base case: If we reach the end of the string, no more lookups needed
if index == len(S):
return 0

# If result is already computed, return it from memo
if memo[index] != -1:
return memo[index]

# Initialize min_lookups as a large number
min_lookups = infinity

# Try every possible substring starting from index
for end from index+1 to len(S):
word = S[index:end]

# Check if the substring is a word in dictionary
if isWord(word, D):
# Calculate lookups required for the remaining part of string
lookups = 1 + minLookups(S, end)

# Update min_lookups with the minimum lookups found
min_lookups = min(min_lookups, lookups)

# Store the result in memo
memo[index] = min_lookups
return min_lookups

# Initial call to the recursive function
result = minLookups(S, 0)

# If result is infinity, the string cannot be segmented
if result == infinity:
return -1
else:
return result