3
\$\begingroup\$

A few days ago I learned about the dynamic programming approach to problem-solving; the thing is, I'm still not sure I am fully grasping the concept.

I decided to write an algorithm that takes a single String of uppercase letters, s, and split it into substrings based on a dictionary I have provided. My algorithm works as expected, although I'm not sure if i'm using the dynamic programming approach correctly. From what I understand, DP uses an array which holds solutions to the subproblems of a larger problem. This was my goal with the result array. Here is my simple program to demonstrate a solution to the problem:

import java.util.Scanner;

class WordBreak
{

    static String[] result;
    static String[] dictionary = {"I", "THE", "ABORT", "PLAN", "MEET", "CONFIRM", "AT",
                                  "DARK", "CABIN", "PROCEED", "MISSION", "MISS",
                                  "CHOCOLATE", "ALIENS", "CANNIBALS", "SAUCE"};

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String str = in.next();
        int size = str.length();
        result = new String[size];
        print(str, 0);
    }
    //method which recursively breaks input string into substrings
    //which are stored in an array and, if they are English words, then printed
    static void print(String str, int ind)
    {
        //each recursive call shortens the input string until length is 0
        int length = str.length();
        //if length is 0, then print the resulting substrings to decode
        //the message
        if(length == 0)
        {
            for(int i = 0; i < ind; i++)
            {
                System.out.print(result[i] + " ");
            }
            System.out.println();
            return;
        }
        //if a valid substring of the dictionary, add it to result array and recur
        for(int i = 1; i <= length; i++)
        {
            if(valid(str.substring(0, i)) == true)
            {
                result[ind] = str.substring(0, i);
                print(str.substring(i), ind + 1);
            }
        }
    }
    //valid function returns true iff string s is an English word (in the dictionary)
    static boolean valid(String s)
    {
        boolean result = false;

        for(int i = 0; i < dictionary.length; i++)
        {
            if(s.equals(dictionary[i]))
            {
                result = true;
                break;
            }
        }
        return result;
    }
}

Given the input string of "ABORTTHEPLANMEETATTHEDARKCABIN" the algorithm does accurately print out "ABORT THE PLAN MEET AT THE DARK CABIN".

My question is, is this a proper dynamic programming approach? If not, what potential changes could I make to implement DP? My main goal here is to make sure I am effectively grasping the concept.

Lastly (kind of off topic), what would the big O of this algorithm be? My analysis tells me either \$O(n^2)\$ or \$O(n^3)\$ depending on how you look at the substring(i, j) method call. This is for my own curiosity to see if I'm analyzing it correctly.

\$\endgroup\$
  • \$\begingroup\$ To use dynamic programming, you have to be able to split your problem into parts which have a high probability to occur repreatedly. I don't see how this applies to your problem statement. Classic examples are computations like factorials or fibonacci numbers. Especially have a look at the fibonacci example in en.wikipedia.org/wiki/Dynamic_programming \$\endgroup\$ – mtj Apr 10 '18 at 6:21
1
\$\begingroup\$

Your big O is roughly O(N^2) if you consider your dictionary to be static.

I don't see anything in your solution that I would classify as dynamic programming. Maybe you could make a DP solution by pre-parsing your dictionary so you don't check substrings multiple times but instead check each letter against each still-matching word. Some more test cases might turn up some interesting bugs, too.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your input, this exactly what I needed. I would upvote but this is the first time ive used this portion of stack-exchange. The complexity is acceptable enough, but I would like to attempt a DP variant. \$\endgroup\$ – Pat Apr 10 '18 at 3:55
1
\$\begingroup\$

Based on this post it seems substring is O(n) time complexity (since java 7). Given that you're actually running substring(i,j)for each possible i and j this means your total time complexity becomes O(n³).

Given that you only actually call the recursion if the current substring is valid it's not as bad as it looks though.


According to wikipedia:

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.

Your current solution does break it up into sub problems and uses the solution of what was before the current substring. However you don't re-use anything calculated for the end of the input.

With the dictionary you have now it also doesn't matter at all.

To show you what I mean let's take a look at another artificial dictionary:

static String[] dictionary = {"A", "AB", "B", "CCC"};

What happens if we use the input string "CCCABBCCC?

You'll find the first CCC once which is good. Then you start handling "A". You'll find "B", another "B" and "CCC".

Your algorithm then backtracks to right after "CCC" again and finds "AB". Now it has to search for possible wordts in the last 4 letters again, but we already checked this right before!

A DP solution would have a way to store all possible solutions found for each "future" index.

An important thing to note here is that it doesn't have to be an array. It can be anyway possible as long as you don't need to calculate this "subproblem" a second time.


I do agree with mtj's comment that this problem doesn't really gain much from using dynamic programming. There is a big memory cost to store sub results which you'll probably never use again.

Finding fibonacci numbers is one of the most obvious simple examples that massively gain from a DP approach. Well, at least if you want to find more than 1 fib number and want to reuse any calculation don't from finding an earlier input number. Don't use DP for finding a single fib number since you can solve it in O(n) with just storing the previous 2 steps.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.