Problem 4. You are given an array of characters s[1 : n] such that each s[i] is a small case letter from theEnglish alphabet. You are also provided with a black-box algorithm dict that given two indices i, j e [n],dict(i, j) returns whether the sub-array s[i : j] in array s forms a valid word in English or not in O(1) time.(Note that this algorithm is provided to you and you do not need to implement it in any way).Design and analyze a dynamic programming algorithm to find whether the given array s can be partitionedinto a sequence of valid words in English. The runtime of your algorithm should be O(n2).Example: Input Array: s =[maythe forcebeuwithyou].Assuming the algorithm dict returns that may, the, force, be, with and you are valid words (this means thatfor instance, for may we have dict(1,3) = True), this array can be partitioned into a sequence of valid words.

Answered: Problem 4. You are given an array of…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

Problem 4. You are given an array of characters s[1 : n] such that each s[i] is a small case letter from the
English alphabet. You are also provided with a black-box algorithm dict that given two indices i, j e [n],
dict(i, j) returns whether the sub-array s[i : j] in array s forms a valid word in English or not in O(1) time.
(Note that this algorithm is provided to you and you do not need to implement it in any way).
Design and analyze a dynamic programming algorithm to find whether the given array s can be partitioned
into a sequence of valid words in English. The runtime of your algorithm should be O(n2).
Example: Input Array: s =
[maythe forcebeuwithyou].
Assuming the algorithm dict returns that may, the, force, be, with and you are valid words (this means that
for instance, for may we have dict(1,3) = True), this array can be partitioned into a sequence of valid words.

Expert Solution

Step 1

The algorithm in pseudocode is below:

function canPartition (s, start = 1):
    len = length (s)
    for i in len to start + 1 with step -1:
        if dict (start, i):
            if i == len:      // finished, successful partitioning
                return True 
            endif
            if canPartition (s, i + 1):
                return True
            else:            // no partition possible, need to try with another i
                continue 
            endif 
        endif 
    endfor 
    return false 
end function

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions