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…

C++ for Engineers and Scientists

4th Edition

ISBN:9781133187844

Author:Bronson, Gary J.

Publisher:Bronson, Gary J.

Chapter7: Arrays

Section7.6: The Standard Template Library (stl)

Problem 8E

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