[LeetCode]Word Break...Wait, it's more than Word Break...

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Tags :  Dynamic Programming

I have a friend who interviewed with FaceBook today, and was asked for this question.  

For me , till now I am still a 'young' coder with only 8 months of computer science experience and only a little time spent on LeetCode or CodeChallenge .  I am still kind of forming my perception of what does it mean by solving A problem through coding.

Even without the tag, I should feel this problem is a typical DP problem.  I will talk about this later.

For me, at this stage, I still feel recursion way of coding is more attractive and elegant. 

When first saw this problem, thing came out in my mind is DFS.  What is DFS? Maybe rigorously I should not mess the conception of DFS with recursion, but DFS always indicates recursion. Recursion's style is going deeper, deeper, till deepest and then turn back. 

Recursion's logic is you are repeating some process on subproblems.  

To understand which way is vertical, it is helpful to compare with which way is horizontal 

Firstly, when I try to summarize this question, I came up something like:

Depth First :

  l     eetcode  

   I     e     etcode      

    I      e    e     tcode    

     ...

    Breadth First

     l     eetcode     le etcode    lee  tcode   leet code ...

     For deep first search, I want cut into as many pieces as possible, till all pieces consist of one letter.

     For breadth first, I want first examine all one cut cases, then all two cuts cases, so on so forth. 

Till now, I am so lost. 

After thinking for quite a while, the above illustration is right.

If I reorganize it ,

    Breadth First(lvl 1)

  l     eetcode  ->    le etcode ->   lee  tcode ->  leet code ...

    Depth First

  l     eetcode 

     Breadth First (lvl 2)

  I     e     etcode      -> l    ee    tcode -> l   eet    code ....

    Depth First

   l    e      etcode

     Breadth First (lvl 3)

   I     e     e    tcode   -> l     e    et    code -> l     e    etc    ode ...       

     ...

     Now it is clear, if we want to recursively solve this problem, this is a typical DFS. I have done some recursive coding on topics of Binary Tree and Binary Search Tree. In the recursion function, I will have a part like first do something on left node, then on right node. Think about this process, once we call the function itself on left node, we are now in a DFS style.  In each function, your Breadth is 2, because you first iterate on left node, then right node. But you never move to the right node, until the function on left node returns. When will it return? When finally the last left node meets the return condition specifying by the recursion function. 
       However, in this breakword problem, instead of having breadth equal 2, we have  len(s) as our breadth. The thing we repeating doing recursively is that we check and cut the input string, and all those possible cuts are indicated by the Breadth. We will call recursive function on our every cut first before moving to next possible cut, so this is DFS.
         See the primitive DFS code:

def wordBreak(s,wordDict):
        if s in wordDict :
            return True
        elif s not in wordDict and len(s) == 1:
            return False
        else:
            for bp in xrange(1,len(s)-1): ##Breadth
                if (wordBreak(copy.copy(s[:bp]),wordDict) and wordBreak(copy.copy(s[bp:]),wordDict)):##Depth
                    return True
            return False

I don't want to discuss how to decide the return condition here, only focus on what exactly is a DFS, for now I should know for sure, there must be a return condition.

This function must be very time costing. If it is a long sting, for every possible substring, and for the substring of substring... we iterated over their length. Imagine how many loops there could be! It will grow exponentially  ! The number of loops are n^n !   How do we get the power n here? For one loop, it costs O(n), and each level has a loop, and the depth is n, so there are n level which means n loops! Think about why the depth is n.

The code is elegant in appearance, but its performance is ... ugly. Think about it, do we really need to go through 'each breadth' so completely? Is there any condition can help us skip some 'hopeless' 'breadth', so we can move quickly to next 'breadth'? 
        See the improved DFS code:

def wordBreak2(s,wordDict):

        if s in wordDict :
            return True
        elif s not in wordDict and len(s) == 1:
            return False
        else:
            for bp in xrange(1,len(s)):
                if s[:bp] not in wordDict:
                    continue##we skip this 'breadth' without wasting time digging deeper
                else:
                    if wordBreak2(s[bp:],wordDict): ##we digger deeper
                        return True ##once we get one instance, we can return, otherwise move further to next 'breadth'
            return False

Long for short, this improved version is much much faster on average,  but we could adversely design cases which make this version also end up with time complexity n^n. Think about it!

It seems I have strayed away too far... I was thinking about writing DP in this post.

....
In order to avoid worst n^n cases, we need to use DP. What is DP and why DP?
I have been starting to think about this concept recently thought I first leaned it like 4 months ago in my algorithm class. 
DP is dynamic programming...if a problem could be divided into subproblems, then this may indicate DP.
Why DP, DP is time safe. You will never get exponential time complexity which takes forever. 
Always, DP and recursion indicate each other. They all rely on same relation between subproblems and problems. 
So, what is the relation here taken use by the recursive function ? Say the key line in primitive version:

if (wordBreak(copy.copy(s[:bp]),wordDict) and wordBreak(copy.copy(s[bp:]),wordDict)):##Depth
                    return True

The relationship should be clear, cut the sting into two pieces, if each of them satisfies the requirement, the string satisfies. The subproblem is on the substring. We solve the subproblems to solve the problem. 

Let's now think about how to build up the solution from subproblems. Notice subproblem also has its subproblems, what would be the subbest-problem. ..

It turns out it relates to the return condition in the recursion function.

        if s in wordDict :
            return True
        elif s not in wordDict and len(s) == 1:
            return False

First look at elif part, we can realize a letter is the subbest-problem...

What is the if part? think about it and we will see how to use it in DP.

(It turns out that the if part is actually part of relationship we described before but at that time, omitted this possible relation. Because this is not a relation between subproblems and problems but instead a self-relation. The problem could possibly be solved without referring to any subproblem, or from another perspective, a string could be divided into a null sting and itself!)

From the subbest-problem, we will build up towards the problem. Say i and j are the index of the string. for i, j in [0,len(s)-1], we want to know if [i,j] satisfies the requirement. 

    def wordBreak( s, wordDict):
        l = len(s)
        dp = [[False]*l for i in xrange(l)]
        for n in xrange(0,l):
            for i in xrange(0,l):
                j = i+n
                if j > l-1:
                    break
                if s[i:j+1] in wordDict:
                    dp[i][j] = True
                else:
                    for k in xrange(i,j):
                        if dp[i][k]  and dp[k+1][j] :
                            dp[i][j] = True
                            break
        return dp[0][l-1]
        

    
I am tied ... but excited to observe so much correlation between recursion solution and DP solution. Let's summarize quickly and I am going to have a complete(hopefully) and in depth DP post later this summer.

Conceptually, let's think about the way recursion do things. Notice it call itself, and all local variables are on stack(I know this is not true for Java or python ) 

, ok, even though you have them on heap (say java, except buildin type, all on heap), when out of the scope, stack variable gonna vanish and those on heap will be garbage collected, actually no matter where the variable are located, outside the function inside which it is defined, you can't refer to it unless you return it.Whatever  the point is that you can't retrieve them any more.

But look at DP, it is more foresight. Since recursion computes the things again and again, why not record them and retrieve them whenever needed in the further.(I know it is not convincing to just say recursion computes same thing many times, think about those subproblems, they are overlap very much!)

The more interesting point I want to make is that DP is actually exactly a more smart and better-planning version of recursion. In Recursion, we have a return condition to stop it, in DP we have base problem to start it. In Recursion, we use the relation to divide problem into sub-problems, in DP we use the same relation to combine sub-problems  into problems. So the point should be clear, Recursion is TOP-DOWN, and DP is BOTTOM-UP. 

That's all for this question. Days ago I saw a very nice way of building up a 2-D dp matrix, plus the way which this problem use, I know three style of building the matrix up now. But no matter how fancy the matrix is built up, it is decided by the relation!