Wildcard matching

Leetcode link. If you are only interested in Yu's code's explanation, jump to here:

Q:

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

Tag of this problem is DP + Greedy. Nice tags explain everything.

The following explanations and code pieces are mostly inspired by link, it seems everyone is using this solution. To make things easier, I will call string s "string", and string p "pattern" from now on. It would be fun to have wildcard in both string and pattern, but for now we restrict wildcard to appear only in the pattern.

Basic idea:

DFS:

So we have three categories of pattern chars, normal ones (anything other than '?' and '*'), single-all matching char ('?') and the most interesting multi-matching char('*'). One can easily come up with:

bool match(string, strptr, pattern, patptr) {
    if (pattern[patptr] != '*' &&  pattern[patptr] != '?')
        return ( string[strptr] == pattern[patptr] && 
                 match(string, strptr+1, pattern, patptr+1) );
    else if (pattern[patptr] == '?')
        return match(string, strptr+1, pattern, patptr+1);
    else
        return ( match(string, strptr, pattern, patptr+1) || \
                 match(string, strptr+1, pattern, patptr+1));
}

Don't even bother trying this in the online judge system. The time complexity is definitely exponential with exponential level memory requirement.

Dynamic programming I:

With that recursive formula in mind, let's transform it to bottom-up DP. In DFS recursive, we are looking forward to chars behind us, In bottom-up DP, we are using the information we already calculated, thus we are looking backward. When a '*' appears, we  match backward instead of forward. We use star to cancel the corresponding string char, pushing the problem back one string char, or we use the star to cancel nothing. Hard to explain without figures:

So the left one is using the star to cancel the current char in string, and leave the star untouched. Now the problem is traced back to whether we should use star to cancel string[i].
The right one is using the star to cancel nothing. Now the DP formula is:

bool match(stringm, strptr, pattern, patptr) {
    if(memoizationTable[strptr][patptr] has any valid info) 
        return memoizationTable[strptr][patptr];
    bool ret;

    if (pattern[patptr] != '*' &&  pattern[patptr] != '?')
        ret = ( string[strptr] == pattern[patptr] && 
                match(string, strptr-1, pattern, patptr-1) );
    else if (pattern[patptr] == '?')
        ret = match(string, strptr-1, pattern, patptr-1);
    else
        ret = ( match(string, strptr-1, pattern, patptr) || \
                match(string, strptr, pattern, patptr-1)); 

    memoizationTable[strptr][patptr] = ret;
    return ret;
}

Now the complexity is somewhat acceptable. With some memory optimization, one can easily come up with a solution of O(MN), O(N) complexity.
Try this with online judge system, still TLE.

Dynamic programming II:

Now that TLE assures me that this problem itself is special, conventional DP technique needs to be altered. There must be something unique here. After some careful thought, state machine and DFA stuff come back to my mind again. Check KMP algorithm and this post for more state machine ideas.

We have three categories, regular chars, '?' chars, and the annoying '*' chars. When the DFA is constructed, regular chars and '?' chars are all very easy to handle since one will only use this char once. The '*' char can be used for multiple times, or none at all, thus critical point is the '*' char. Say I have pattern "*a*b*c". At the first star I can use it for k1 times, second star I can use it for k2 times, The solution to this wild card problem can be represented by an array of [k1, k2, k3, ...] I can uniquely come up with one way to match the pattern to the string. Wait a sec, this is not DP, this is brute force. Where is the overlapping subproblem?

Consider this case

string:  aaaaa cX
pattern: *a*a* c

While searching, suppose we are now having first star representing 1 '?', second star representing 2 '?', then when we visit the third star, we know it will fail. Next time we have first star representing 2 '?', second star representing 1 '?', when we visit the third star we can just give up. since now the pattern is aligned exactly the same as last time. So I was thinking using an offset to record this. Mark each star as one state, for each state, if an accumulative offset fails, record it, so next time it does not need to calculate again.  Code looks like this. Still fails online judge.

Dynamic programming III:

OK, more pruning is needed. First pruning, when the string pointer reaches end of string, but pattern pointer is not at the end yet, what should we do?

Case 1: If the remaining part of pattern is full of '*', we are good.
Case 2: Else, we have a mismatch. Check this (Upper one is string, lower one is pattern, this offset thing means I will use the star to represent the whole offset section in string):

So now we have a mismatch, and section b contains character that is not '*'. In this case, are we 100% sure that pattern will not match target string? Notice the only tunable parameter here is offset, which can only be increased, not decreased, since the program will try offset 0 first, then offset 1, then offset 2.... So the question is, is it possible to achieve matching between target string and pattern only by increasing offset?

No. when we increase offset, suppose we get this:

Since b is still here, now d+b string still cannot give us a pass.

So we have:

When target string matches to its end:
1. if pattern reaches its end, pattern matches target string.
2. if pattern is not at its end, but left with bunch of '*'s, pattern matches string.
3. if pattern is not at its end, with chars other than '*' left, pattern will not match string.

With this pruning, along with above dynamic programming trick, this code piece barely passes online judge. AC time 1392ms. Yes, more than 1 sec.

Greedy:

More pruning! See I changed the section title. (This idea is borrowed from Yu's code.)
There is a very important backtracking procedure in the previous dynamic programming. Check this graph out.

In this case, since segment b will not match segment c, we have a fail. Moreover, I assume that no matter how I tune offset 2, it will always give me a fail. Now I'm faced with this question:
Do I need to back track, and increase offset 1 such that the following situation might occur?

Answer is no.

Why? If this happens, then if I set offset 2 to offset1'-offset1+offset2', we can use offset1 and offset2 to achieve the same goal. Here offset1'-offset1+offset2' is definitely positive.

So we have:

When we have a mismatch, we only tune the nearest offset, if tuning the nearest offset cannot solve this problem, then pattern cannot match target string.

This means we only need to record the nearest offset. Memory space requirement O(1).

Conclusion:

Combining dynamic programming III and greedy, wildcard can be solved by using this code piece:

    bool isMatch(const char *s, const char *p) {
        const char* strptr = s;
        const char* patptr = p;
        
        const char* lastStrPtr = NULL;
        const char* lastPatPtr = NULL;
        while (*strptr) {
            if (*strptr == *patptr || *patptr == '?') {
                strptr++; patptr++;
            }
            else if (*patptr == '*') {
                lastStrPtr = strptr;
                lastPatPtr = patptr++;
            }
            else if (*strptr != *patptr) {
                if (!lastStrPtr) return false;
                strptr = ++lastStrPtr;
                patptr = lastPatPtr + 1;
            }
        }
        while(*patptr == '*') patptr++;
        return !(*patptr);
    }

AC time around 100ms. Very nice greedy approach.

Grammar candy: Lambda expression (closures) in C++11

Useful links: Alex Allain's blog. Cheatsheet (Chinese).

Basic structure of lambda expression:

[capture specification](argument list)->return type {function body}

Example:

int main() {
    auto f = [](){cout<<"hello world";};
    f();
    return 0;
}

Argument list is what we needed in the lambda function. Just like:

int main() {
    auto f = [](int v){cout<<v<<endl;};
    f(1024);
    return 0;
}

Capture specification is fun, it means we can use external data/variable (with respect to lambda function itself) in the lambda function. Based on the way we pass the external data/variable, there are several cases:

1. [], Empty: No external data/variable is needed in the current lambda function. Just like all the cases above;
2. [=]: Pass all visible data/variable with respect to the lambda function into lambda function, by value.

   int main() {
       int a = 1;
       int b = 2;
       auto f = [=](int c){cout<<(c+a)<<' '<<(c+b);};
       f(10);
       return 0;
   }
   

   Output 11 and 12.
3. [&]: Same as above, only difference is pass by reference.

   int main() {
       int a = 1;
       auto f = [&]{++a;};
       f();
       cout<<a;
       return 0;
   }

   Output 2.
4. [this]: pass lambda function class to lambda function.

   struct s{
       int v;
       s(int val):v(val){};
       void f(){ ( [this]{cout<<++v;} )(); }
   };
   
   int main() {
       (new s(3))->f();
       return 0;
   }

   Output 4.
5. [var_name]: Only pass variable var_name to lambda, by value.
6. [&var_name]: Same as above, only difference is pass by reference.
7. [a, &b]: Pass variable a by value, b by reference.
8. [=, &a, &b]: Pass variable a and b by reference, all other visible variables pass by value.
9. [&, a, b]: Inverse of case 8.

   int main() {
       int a = 1;
       int b = 2;
       int c = 3;
       ([=, a, &b]{cout<<a<<b++<<c<<endl;}) ();
       cout<<a<<b<<c;
       return 0;
   }

   Output 123,133. Don't try to to ++a inside lambda function, this will throw an error stating a is read only.

Return type:

When lambda contains more than one return value, C++ standards say you better give it a return type, just like:

int main() {
    auto abs = [](int a)->int{if(a>=0)return a;
                           else return -a;};
    cout<<abs(-3)<<abs(-2)<<abs(-1)<<abs(0);
    return 0;
}

If you try this in ideone, it will not complain if you missed the ->int part, but that is because of GCC. C++ standard say you should explicitly denote the return type.

Alex also presents a very fun concept, Delegate.I am still a newbie, thus I'll use Alex's case and build a similar test case:

#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
using namespace std;

struct c1{
    vector<int> v;
    c1(vector<int> val):v(val){}
    
    void modifyV(function<string (int)> functionHandle) {
        if(functionHandle) {
            for_each(v.begin(), v.end(), \
            [&](int e){cout<<functionHandle(e);});
        }
    }
};

struct c2{
    int record;
    c2():record(0){};
    string c2func(int val) {
        record = max(record, val);
        return val%2?"odd ":"even ";
    }
    void disp() {
        cout<<"\nmax number is "<<record;
    }
};

int main() {
    vector<int> v{1,2,3,4,5};
    c1 t(v);
    c2 t2;
    t.modifyV([&](int val){return t2.c2func(val);});
    t2.disp();
    return 0;
}

Output is:

odd even odd even odd 
max number is 5

So what I did was I use class c2 to process c1's data (determine whether it is odd number or even number) and record c1's data's maximum number. The connection is built by code on line 34. This lambda function use & to take in t2 and passed it to t.

This is quite fun, a more interesting code can be found in Alex's post. He also talks about how to receive a lambda function as input by using std::functional<type>, function handle as parameter.

Minimum window substring

Leetcode link.

This is suppose to be an easy question since I have already read through stormrage's post and thought I have mastered every detail about this code. But eventually it took me almost 3 hours straight to figure out a nice and clean code.

There are several things that one should notice in designing a robust algorithm for this problem:

1. loop invariant: count <= total required chars. (excessive chars not accounted). If count < total required chars, we are building the first matching window. thus shrinking left edge is not necessary. Else if count == total required chars, Current window is either a half finished first time window or perfect left edge window with "one extra required char on the right edge " window. In both cases we can start shrinking left edge.
2. We do not have to write a separate code block to do first time window matching because either the first matching or second matching requires left shrinking. Thinking of S = "aab" and T = "b".

So eventually with some modifications I come up with the following code. Alas, always think carefully before you start coding.

string minWindow(string S, string T) {
    if(S.size() < T.size() || !T.size()) return *(new string);
    vector lmt(256);
    for(auto c:T) lmt[c]++;
    vector ct(256);
    
    int minLen = INT_MAX;
    string ret;
    
    int a0, a1, count;                              // left and right edge pointer.
    count = 0;
    for(a0 = 0, a1 = 0; a1 < S.size(); a1++) {      // do right edge expand at loop start
        if(!lmt[S[a1]]) continue;                   // invalid char, keep expanding
        if(ct[S[a1]] < lmt[S[a1]]) count++;         // char is needed now, increase count
        ct[S[a1]]++;                                // hasFound array+1
        
        if(count == T.size()) {                     // loop invariant met, now do shrinking
            for(;a0 < a1; a0++) {                   // shrinking....
                if(!lmt[S[a0]]) continue;           // invalid char, keep shrinking
                ct[S[a0]] --;                       // good char, try hasFound--
                                                    // before shrinking
                if(ct[S[a0]] < lmt[S[a0]]) {        // oops, should not delete this char.
                    ct[S[a0]]++;                    //   roll hasFound back.
                    break;                          //   don't move left edge pointer a0
                }                                   // it's ok to remove this char, keep
                                                    // shrinking
            }
            
            if(a1 - a0 + 1 < minLen) {              // one min window found. update
                minLen = a1-a0+1;
                ret = S.substr(a0, a1-a0+1);
            }
        }
    }
    
    if(minLen == INT_MAX) return *(new string);     // INT_MAX is acting as safeguard.
    return ret;
}

Distinct Subsequence

Leetcode link.

Q: Given a string S and a string T, count the number of distinct subsequences of T in S.
Example: S = "rabbbit", T = "rabbit". Return 3.

This question itself is already hard to understand. I failed in creating a DP formula for it (fired). But with KMP in mind, I come up with another method that use finite state machine to do this problem. Complexity(O(m*n), O(n)), where m and n are length of S and T.

Other guy's method (DP based):

Use num[i][j] to save the number of distinct subsequences of T(0, j) in S(0, i).
Then

1. if T[j] != S[i], Formula num[i][j] = num[i-1][j].
2. else we have two options for the new char S[i], either we take it (num[i-1][j-1]) or we don't take it (num[i-1][j]). Formula num[i][j] = num[i-1][j-1] + num[i-1][j].

Space optimization technique can be used just like what I did in this post. Final complexity (O(m*n), O(n)). The following code is borrowed from this post(Chinese).

int numDistinct(string S, string T) {  
    // Start typing your C/C++ solution below  
    // DO NOT write int main() function  
    int match[200];  
    if(S.size() < T.size()) return 0;  
    match[0] = 1;  
    for(int i=1; i <= T.size(); i++)  
        match[i] = 0;  
    for(int i=1; i<= S.size(); i ++)  
        for(int j =T.size(); j>=1; j--)  
            if(S[i-1] == T[j-1])  
                match[j]+= match[j-1];  
    return match[T.size()];  
}  

My state based method:

So each char in the T string is treated as a state. This state thing basically means at current state, if  I received the char I want from S, I can either take this char and progress to the next state, or I do not take this char. Example:

For target T = "rabbit" . I have state 0 to 5 standing for current matching state. If my current state is at 4, which is character "i", and I receive a char "t" from S, I can either progress to the next state "t", or I disregard this "t" and wait for the next "t" to appear. Basically similar to the DP formula:  num[i][j] = num[i-1][j-1] + num[i-1][j].

I construct a state count array ct of size T.size() and initialized as all 0 except for the first state ct[0] = 1.  This means at character i, how many states are waiting for the same T[i] in string S to appear. This seems hard to explain. Let me draw some figures.

So now, 1 state is waiting for character "r" from string S. No one is waiting for "a" to "t".

Send a "r" from string S.

This "r" can either be consumed or not. If consumed, we will wait for an "a" then, if not, we will still wait for a "r":

Send an "a" from string S.

First we consider the one waiting for an "a", as last time, it can choose to consume this "a" or not consume this "a". As to the one waiting for an "r", it will not progress. (Similar to DP formula num[i][j] = num[i-1][j]).

Send a "b" from string S.

This is the same as last time. I will just skip it and only paste the drawing.

Send another "b" from string S.

Now this is the fun part, I now have state 2 and state 3 all waiting for this coming "b". For state 2, if I consume this "b", it will be converted to state 3. But this newly converted state 3 cannot consume "b" again since I only received one "b" from S. On the other hand, those already sitting at state 3 can consume this "b" and get converted to state 4. Thus I will do state 3 first, and then do state 2.
For state 3 waiting for "b":
 (Green arrow means consume this "b", red means do not consume this "b"):

Then state 2 waiting for "b":

This is just like memory optimization, from last state to the fist state instead of first state to the last.
Final ct after this step:

Send the third "b" from string S:
Those at state 4 waiting for "i", at state 1 waiting for "a", at state 0 waiting for "r" will not be affected. Use similar analysis method, one can come up with this final ct array:

Send an "i" from string S:
Same as send "a" or send "r". Final ct array:

Send a "t" from string S:
Now those state waiting for "t", if they decide to consume this "t", then we will have 3 subsequences that matches the requirement. If they decide not to consume this "t", we leave it in the ct array.
Final ct array should be exactly the same as the above one, while all the "overflow" states get captured in a return variable.

Now we are at the end of string S. Loop ends.

Code looks so similar to DP version. (in fact, you can say I am using DP since this ct array is basically the memoization step).

int numDistinct(string S, string T) {
    //corner cases
    if (!S.size() || !T.size() || S.size() < T.size()) return 0;

    //state counter array
    int* ct = new int[T.size()]();
    ct[0] = 1;
    int ret = 0;
    for (int i = 0; i<S.size(); i++)
        for (int j = T.size() - 1; j >= 0; j--)
            if (S[i] == T[j])
                if (j == T.size() - 1) ret += ct[j];
                else ct[j + 1] += ct[j];
    
    return ret;
}

Playable version can be found here.

Leetcode: Best Time to Buy and Sell Stock (Extension, DP)

Leetcode link to original problems:
BS1: https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/ (O(n), O(1))
BS2: https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ (O(n), O(1))
BS3: https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/ (O(n), O(n)) or (O(n), O(1))

Extension to buy and sell stock problem:

Q: Say you have an array of size n, for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions.
Assume this array is named as prices[].

First step: Basic DP formula

Idea comes from lrd15's awesome post (link). Another idea that I found is this post (Chinese), which is quite hard to comprehend for me though.

We are now trying to handle a generalized problem that can be represented as finding profit[i][k], where the first index i represents day i, and second index k represent maximum number of transactions so far. As usual, for problems that aim to find maximum/minimum result, we break it to one subproblem that contains the current index, and one subproblem that does not contain the current index. This problem is no different.

Our problem:

For profit[i][k], we seek:

1. Subproblem 1: No transaction ends at day i. =>           profit[i-1][k] = S1
2. Subproblem 2: The last transaction ends at day i => S2

What we need to do is to find out which one is bigger? S1 or S2. Then profit[i][j] = S1>S2?S1:S2.
This S2 can be further decomposed to:

Suppose the last transaction starts at day j, then
S2 = maximum { profit[j][k] + (prices[i] - prices[j])}, where j is [0, i).
Now we can write the basic DP formula as:
profit[i][k] = max{ profit[i-1][k], maximum{profit[j][k] + (prices[i] - prices[j]) | j in [0,i)} }

A bottom-up implementation using (O(kn^2), O(kn)) time-space complexity.

int maxProfit(vector<int> &prices, int times = 2) {
 // corner cases
 if (prices.size() <= 1) return 0;

 // define profit[i][k] at i day, at most k transactions
 // 
 // the recursive equation is:
 // profit[i][k] = max(profit[i-1][k], ->last trans@today
 //       max(prices[i]-prices[j]+profit[j][k-1]) ->last trans@day j)
 //       here j is at range [0, i-1]
 // can also be rewritten as 
 // profit[i][k] = max(profit[i-1][k], 
 //                    prices[i]+max(profit[j][k-1]-prices[j]))
 int numOfDays = prices.size();
 int numOfTrans = times;

 int** profit = new int*[numOfDays];
 for (int i = 0; i < numOfDays; i++)
  profit[i] = new int[numOfTrans+1]();

 for (int i = 1; i < numOfDays; i++) {
  for (int k = 1; k <= numOfTrans; k++) {
   // find max(profit[j][k-1] - prices[j]) for j [0,i)
   int S = INT_MIN;
   for (int j = 0; j < i; j++) {
    int temp = profit[j][k - 1] - prices[j];
    if (temp>S) S = temp;
   }
   int term1 = profit[i - 1][k];
   int term2 = prices[i] + S;
   profit[i][k] = term1 > term2 ? term1 : term2;
  }
 }
 return profit[numOfDays - 1][numOfTrans];
}

Playable version here. Leetcode TLE since this is basically n^2 complexity.

Second step: Optimization

Now this is the tricky part since it's all about math. Let's take a look at the DP formula again:
profit[i][k] = max{ profit[i-1][k], maximum{profit[j][k] + (prices[i] - prices[j]) | j in [0,i)} }

When we calculate maximum{profit[j][k] + (prices[i] - prices[j]) | j in [0,i)} part, we notice prices[i] term can be extracted, changing the original DP formula to:
profit[i][k] = max{ profit[i-1][k], prices[i] + max{profit[j][k-1] - prices[j]} }
and the term max{profit[j][k-1] - prices[j]} can be further DP since this is a running maximum value problem.

If we write:
S[m][k] = max{ profit[j][k-1] - prices[j] | j in [0, m)}
then based on running maximum:
S[m][k] = max{ profit[m-1][k-1] - prices[m-1], S[m-1][k]}
Now we can decompose the modified DP formula to a DP equation set:
S[i][k] = max{ profit[i-1][k-1] - prices[i-1], S[i-1][k] }
profit[i][k] = max{ profit[i-1][k], prices[i] + S[i][k] }

This is the end of time optimization.

Space optimization is easy to see. profit[i][k] only depends on the last row. So does S[i][k]. Thus using bottom-up space optimization rule, we come up with the following code: (O(kn), O(k))

int maxProfit(vector<int> &prices, int times=2) {
    // corner cases
    if (prices.size() <= 1) return 0;

    // define profit[i][k] at i day, at most k transactions
    // 
    // the recursive equation is:
    // profit[i][k] = max(profit[i-1][k], ->last trans@today
    //                      max(prices[i]-prices[j]+profit[j][k-1]) ->last trans@day j)
    //                      here j is at range [0, i-1]
    // can also be rewritten as 
    // profit[i][k] = max(profit[i-1][k], 
    //                    prices[i]+max(profit[j][k-1]-prices[j]))
    // if we write:
    // S[l][k] = max(profit[j][k-1]-prices[j]), (j in [0, l)), then its equation is
    // S[l][k] = max(profit[l-1][k-1]-prices[l-1], S[l-1][k]).
    // Rewrite line 18 equation as equation set:
    //     S[i][k] = max(profit[i-1][k-1]-prices[i-1], S[i-1][k])
    //     profit[i][k] = max(profit[i-1][k], prices[i] + S[i][k])
    //
    int numOfDays = prices.size();
    int totalTransTime = times;
    // only need to construct one row
    // at day 0, no matter how many trans its all 0 profit.
    int* profit_i = new int[totalTransTime+1]();
    int* S = new int[totalTransTime+1]();
    for (int i = 0; i < totalTransTime + 1; i++)
        S[i] = INT_MIN;
    for (int i = 1; i < numOfDays; i++) {
        for (int k = totalTransTime; k > 0; k--) {
            int cand = profit_i[k - 1] - prices[i - 1];
            if (cand > S[k]) {
                S[k] = cand;
            }
            else
                S[k] = S[k];
                
            int term1 = profit_i[k];
            int term2 = prices[i] + S[k];

            profit_i[k] = term1 > term2 ? term1 : term2;
        }
    }
    return profit_i[totalTransTime];
}

Playable version here. Leetcode AC, 52ms.




Update (2014-11-19)
Why this works? Especially the decomposition part where I decompose a double maximization problem into a DP equation set? (Sidenote: Using more space to store intermediate value such that time can be saved).
The problem in this post contains subproblem max{profit[j][k-1] - prices[j]} that has nothing to do with i except in the range of j.
Can I apply this strategy to other DP problems such as "container with most water problem"?

The DP equation in the container problem is:
bestContainer[i] = max{ min(height[i], height[j]) * (j - i) | j in [0, i) }
This problem, on the contrary, does not have an intermediate result that I can store. I can not separate j from i because of the term min(height[i], height[j]).

So when to apply this space vs time strategy? I guess observation is the key. Identify the characteristic of the DP formula and see what you can find.



Update (2015-10-4)
Leetcode created a OJ for this general case. Link. One more pruning is needed to pass the large data set: If transaction time is larger or equal than day size / 2, to make sure no two transactions are overlapping, this problem degenerates to "Best time to buy and sell stock II", which means unlimited sale/buy can be performed. This can be done in O(n) time.