Can Construct

It is Wednesday on a nice and warm day in the Twin Cities of Minneapolis and St. Paul. To be honest with you, it does not matter much if the day is nice or not. I have not been outside today. On the other hand the forecast for Friday, Saturday and Sunday is calling for temperatures in the low 90’s. Hopefully my wife and I will be able to enjoy the days. In particular we are planning on walking early morning so we can avoid the high temperatures. We are planning on grilling and consuming some adult beverages. I believe we are almost out of beer so we might stop by Friday evening after work by the liquor store.

I continue to watch the Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges YouTube video. At this time I have already watched more than half. So far I enjoy the presentations by Alvin from freeCodeCamp.org. He is quite good at it.

At this time the course is shifting to a different yet similar problem. The idea is to use what has been presented so far and adapt it to the next set of similar problems.

Write a function `canConstruct(String target, String[] wordBank)` that accepts a 
target string and an array of strings.

The function should return a boolean indicating whether or not the
`target` can be constructed by concatenating elements of the
`wordBank` array.

You may reuse elements of `wordBank` as many times as needed.

This time we are given a target string and an array of strings that contain words that can be used to construct the target. Stop for a few and think about this new problem in light of the previous ones. Instead of numbers we will be using characters. Instead of subtracting values we will be removing suffixes. We need to figure out a base case. Once we get this done, we can charge on and implement a recursive call to solve the problem.

It is expected that most of the problems will work in a reasonable amount of time. We will then hit a wall and will have to implement memoization to get past the slow problem. It sounds quite familiar.

The author of the video uses JavaScript to solve the problems. In this post we will be using Java and the VSCode IDE on a Windows 10 machine. I believe that Java and JavaScript are quite portable among different platforms.

boolean canConstruct(String target, String[] wordBank) {
}

The signature of the function in question is quite simple. We are given a target string and using the contents from the wordBank array of strings, we need to construct the target. If we can, we return true; otherwise we return false.

I will not go into details explaining the approach to solve the problem. I strongly recommend watching the YouTube video.


cat,dog,mouse
main <<< target ==><==
main <<< wordBank: [cat, dog, mouse]
main <<< canConstruct: true time: 0 ms.
main <<< canConstructMemo: true time: 0 ms.


abcdef
ab,abc,cd,def,abcd
main <<< target ==>abcdef<==
main <<< wordBank: [ab, abc, cd, def, abcd]
main <<< canConstruct: true time: 0 ms.
main <<< canConstructMemo: true time: 0 ms.


skateboard
bo,rd,ate,t,ska,sk,boar
main <<< target ==>skateboard<==
main <<< wordBank: [bo, rd, ate, t, ska, sk, boar]
main <<< canConstruct: false time: 1 ms.
main <<< canConstructMemo: false time: 0 ms.


enterapotentpot
a,p,ent,enter,ot,o,t
main <<< target ==>enterapotentpot<==
main <<< wordBank: [a, p, ent, enter, ot, o, t]
main <<< canConstruct: true time: 0 ms.
main <<< canConstructMemo: true time: 0 ms.


eeeeeeeeeeeeeeeeeeeeeeeeeeeeef
e,ee,eee,eeee,eeeee,eeeeee
main <<< target ==>eeeeeeeeeeeeeeeeeeeeeeeeeeeeef<==
main <<< wordBank: [e, ee, eee, eeee, eeeee, eeeeee]
main <<< canConstruct: false time: 12213 ms.
main <<< canConstructMemo: false time: 0 ms.

The test cases provide two input lines. The first contains the target string. The second line contains a set of strings that we can use to build the target string.

Our test scaffold reads the two input lines and creates and populates the variables. The content of the variables are then displayed. I like to display the values to make sure all is well before starting to attack the problem at hand.

As we can see, there are two implementations of the method in question. The first does not use memoization. The second does.

All the test cases seem to return the same values and both ran in a reasonable short time.

If you look at the last test case, the one without memoization takes about 12 seconds to complete. For this one memoization is required.

    /**
     * Test scaffold
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** initialization ****
        boolean ans = false;
        long start  = 0;
        long end    = 0;

        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));

        // **** read target string ****
        String target = br.readLine().trim();

        // **** read String[] word bank ****
        String[] wordBank = br.readLine().trim().split(",");

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<< target ==>" + target + "<==");
        System.out.println("main <<< wordBank: " + Arrays.toString(wordBank));

        // **** call function of interest and display result ****
        start = System.currentTimeMillis();
        ans = canConstruct(target, wordBank);
        end = System.currentTimeMillis();
        System.out.println("main <<< canConstruct: " + ans + " time: " + (end - start) + " ms.");
        
        // **** call function of interest and display result ****
        start = System.currentTimeMillis();
        ans = canConstructMemo(target, wordBank);
        end = System.currentTimeMillis();
        System.out.println("main <<< canConstructMemo: " + ans + " time: " + (end - start) + " ms.");
    }

Our test code seems to follow closely the description of what we are doing. It reads the two input lines, declares, populates and display their values. The arguments are then passed to the implementations. The result and the time it took to generate the result are displayed.

    /**
     * Return a boolean indicating whether or not the
     * `target` can be constructed by concatenating elements of the
     * `wordBank` array.
     * You may reuse elements of `wordBank` as many times as needed.
     * 
     * Recursive call without memoization.
     * 
     * m = target.length
     * n = wordBank.length
     * 
     * Time: O(n^m * m)  Space: O(m^2)
     */
    static boolean canConstruct(String target, String[] wordBank) {

        // **** base cases(s) ****
        if (target.length() == 0) return true;

        // **** iterate through all the words in the word bank ****
        for (int i = 0; i < wordBank.length; i++) {

            // **** get the prefix from the word bank ****
            String prefix = wordBank[i];

            // **** check if this is a prefix in target ****
            if (target.indexOf(prefix) == 0) {

                // **** extract the suffix from target ****
                String suffix = target.substring(prefix.length());

                // **** make recursive call with the suffix ****
                if (canConstruct(suffix, wordBank))
                    return true;
            }
        }

        // **** cannot construct ****
        return false;
    }

This is the recursive method we are required to write without memoization. It is a good idea to implement the recursion and test it before implementing memoization.

We start by defining the base or end case. In our problem that happens when the target becomes “”.

We then enter a loop which iterates through all the words in the bank. To proceed in order we move in order from the front to the back of the target string. The front represents the prefix and the remainder represents the suffix.

The words in the bank represent the suffixes we can use to process the target string.

We then check if the prefix is part of the target string. If so we extract the suffix and make a recursive call. As soon as we find a set of words that can be used to rebuild the target string we return with a true value. If we cannot find a set of words in the bank, we return false.

    /**
     * Return a boolean indicating whether or not the
     * `target` can be constructed by concatenating elements of the
     * `wordBank` array.
     * You may reuse elements of `wordBank` as many times as needed.
     * 
     * Entry point with memoization.
     * 
     * m = target.length
     * n = wordBank.length
     * 
     * Time: O(n * m^2)  Space: O(m^2)
     */
    static boolean canConstructMemo(String target, String[] wordBank) {

        // **** sanity check(s) ****
        if (target.length() == 0) return true;

        // **** initialization ****
        HashMap<String, Boolean> memo = new HashMap<>();

        // **** recursive call with memoization ****
        return canConstructMemo(target, wordBank, memo);
    }

We now are going to implement memoization. This function represents the entry point for recursion. Note that we create the memo in which we will associate each string with a value (true or false).

We then call the recursive function and return the value from the call.

    /**
     * Return a boolean indicating whether or not the
     * `target` can be constructed by concatenating elements of the
     * `wordBank` array.
     * You may reuse elements of `wordBank` as many times as needed.
     * 
     * Recursive call with memoization.
     */
    static private boolean canConstructMemo(String target,
                                            String[] wordBank,
                                            HashMap<String, Boolean> memo) {

        // **** end cases(s) ****
        if (target.length() == 0) return true;
        if (memo.containsKey(target)) return memo.get(target);

        // **** iterate through all the words in the word bank ****
        for (int i = 0; i < wordBank.length; i++) {

            // **** get the prefix from the word bank ****
            String prefix = wordBank[i];

            // **** check if this is a prefix in target ****
            if (target.indexOf(prefix) == 0) {

                // **** extract the suffix from target ****
                String suffix = target.substring(prefix.length());

                // **** make recursive call with the suffix ****
                boolean ans = canConstructMemo(suffix, wordBank, memo);

                // **** insert key value pair into memo ****
                memo.put(target, ans);

                // **** check if done ****
                if (ans)
                    return true;
            }
        }

        // **** insert key value pair into memo ****
        memo.put(target, false);

        // **** cannot construct ****
        return false;
    }

This is the original function with the necessary changes to support memoization.

The first change is in the end cases. We look for the target string in our memo. If found we return the associated value.

The next change is the addition of the memo argument to the recursive call.

Note that the returned value is put into the memo by associating the target string to the returned value by the recursive call (true or false).

We then check if the ans is true. If so we return from this function.

If our recursive call returns false, then we will save the associated target string with the value false in the memo. We will then return false.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Regards;

John

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.