Longest Common Prefix

class Solution {//straightforward, and easy
public:
    string longestCommonPrefix(vector<string> &strs) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (strs.empty()) return "";
        string result("");
        for(int sii = 0; 1; ++sii){
            for(int vjj = 0; vjj < strs.size(); ++vjj){
                if (sii >= strs[vjj].size() || strs[0][sii] != strs[vjj][sii]){
                  return result;
                }
            }
            result.push_back(strs[0][sii]);
        }
    }
};

Letter Combinations of a Phone Number

Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

class Solution {/*Straightforward, and easy**/
private:
    vector<string> rep;
    vector<string> result;
    void build(string const& digits, int digitIndex, string ss){
        int const num = digits[digitIndex]-'0';
        if (digitIndex + 1 == digits.length()){
            for(int buttonIndex = 0; buttonIndex < rep[num].length(); ++buttonIndex){
                result.push_back(ss+rep[num][buttonIndex]);
            }
            return;
        }
        for(int buttonIndex = 0; buttonIndex < rep[num].length(); ++buttonIndex){
            build(digits, digitIndex+1,ss+rep[num][buttonIndex]);
        }
        return;
    }
public:
    vector<string> letterCombinations(string digits) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (digits.empty()) return vector<string>(1,"");
        result.clear();
        rep.resize(10);
        rep[2]="abc";
        rep[3]="def";
        rep[4]="ghi";
        rep[5]="jkl";
        rep[6]="mno";
        rep[7]="pqrs";
        rep[8]="tuv";
        rep[9]="wxyz";
        build(digits, 0, ""); 
        return result;
    }
};

Length of Last Word

Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example, 
Given s = "Hello World",
return 5.

class Solution {/*Straightforward, and easy**/
public:
    int lengthOfLastWord(const char *s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!s) return 0;
        int size = 0;
        while(s[size]){
            ++size;
        }
        int index = size-1;
        size = 0;
        while(index >= 0 && s[index] == ' ') --index;
        while(index >= 0 && s[index] != ' '){--index; ++size;}
        return size;
    }
};

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Brain activity: Pick a rectangle, with its height being "the height", what's the largest area you can extend?
The expansion can continue to go both directions centered with this rectangle, as long as the others are taller, until you meet the "ditches", which are the first ones shorter.
To accelerate the algorithm to at most O(NlgN), some tricks are needed for finding the "ditch" locations.

Notice that only shorter rectangles can "ditch" the expasion.

So the idea is: If the positions of all the shorter rectangles are known, and sorted in a set, then after is inserted the position of current rectangle, the "ditch" positions are the neighbors!

Considering the duplicate heights (different positions with the same height). Since same heights do not "ditch" each other, so the insertion of positions should occur after the "ditch" neighbors are found.

Step 1: Sort the rectangles by height, from short to tall (hist[]). Their original positions will be recorded in (index[]) in the order of (hist[]).
Step 2: Rectangles from low to high
                 Register height, (h) and current position, (pos)
                 Use this position find the neighbors in (index[]), (leftDitch) and (rightDitch)
                 Calculate the area with the height (h) * (rightDitch - leftDitch -1)
                 Push the (pos) into ditch set (index[])
                 Repeat step 2
Step 3: Find the max area calculated in Step 2. (Can be done O(N) time)


Barely passed the large test.

class Solution {
    struct HPOS{int h;int pos;HPOS(int a, int b):h(a),pos(b){}};
public:
friend    bool operator<(HPOS a, HPOS b){
        return a.h < b.h;
    }

    int largestRectangleArea(vector<int> &height) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int maxArea = 0;
        multiset<HPOS> hist;//height,pos
        for(int ii = 0; ii < height.size(); ++ii){
            hist.insert(HPOS(height[ii],ii));
        }
        set<int> index;//all the short height positions
        for(multiset<HPOS>::iterator it = hist.begin(); it != hist.end();){//from shortest to tallest
            multiset<HPOS>::iterator hBoundEnd = hist.equal_range(HPOS(it->h,it->pos)).second;
            //count how many with the same height
            //at least one, itself
            vector<int> equalIndex;//do not count same height positions
            for(; it != hBoundEnd; ++it){
                equalIndex.push_back(it->pos);
                pair<set<int>::iterator, set<int>::iterator> bound = index.equal_range(it->pos);
                //find the closest left ditch and right ditch
                //bound.first is it->pos itself
             int leftDitch = 0;
          int rightDitch = height.size() - 1;
                if (bound.first != index.begin()){
                    advance(bound.first,-1);
                    leftDitch = *bound.first + 1;
                }
                if (bound.second != index.end()) rightDitch = *bound.second-1;
                int area = (rightDitch-leftDitch+1) * it->h;
                if (maxArea < area) maxArea = area;
            }
            for(int ii = 0; ii < equalIndex.size(); ++ii){
                index.insert(equalIndex[ii]);
            }
        }
        return maxArea;
    }
};

Jump Game II

Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. For example: Given array A = [2,3,1,1,4] The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

/**For example {4,1,1,3,1,1,1}.
Step 1: Start with 4 (index=0), get the furthest range (index=[1,4]).
Step 2: Within the range (index=[1,4]), the furthest one can get using one of the elements in the range, is using 3 (index=3), and the new range is (index=[5,6]). The new range reaches the lastIndex. Done
*/
class Solution {
private:
    int getMaxRangeIndex(int A[], int start, int end){
        int index = start;
        int maxRange = start+A[start];
        for(;start<=end; ++start){
            if (start+A[start] > maxRange){
                index = start;
                maxRange = start+ A[start];
            }
        }
        return index;
    }
public:
    int jump(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (n <= 1) return 0;
        int const lastIndex = n-1;
        int steps = 0;
        int lowBound = 0;
        int highBound = 0;
        while(highBound < lastIndex){
            int ii = getMaxRangeIndex(A,lowBound, highBound);
            ++steps;
            lowBound = highBound+1;
            highBound = ii + A[ii];
        }
        return steps;
    }
};

Jump Game

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

class Solution {
public:
    bool canJump(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (n <= 0) return true;
        int const lastIndex = n-1;
        vector<bool> toLast(n,false);
        for(int ii = lastIndex; ii >= 0; --ii){
            if (ii + A[ii] >= lastIndex){ 
                toLast[ii] = true;
                continue;
            }else{
                toLast[ii] = toLast[ii+A[ii]];
            }
        }//for ii
        return toLast[0];
    }
};

Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Link to the explanation graph

/*passed small test, but did not pass large test.
It is slow due to the overlapping subproblems, and 
it run in exponential time.
 See below for the faster solution.
*/

class Solution {
private:
    bool build(string const& a, string const& b, string const& c,
        int const aii, int const bii){//true-a, false-b
          if (aii < 0 && bii < 0) return true;
          if (aii < 0){
              if (b[bii] != c[aii+bii+1]) return false;
              else return build(a,b,c,aii,bii-1);
          }
          if (bii < 0){
              if (a[aii] != c[aii+bii+1]) return false;
              else return build(a,b,c,aii-1,bii);
              
          }
          if (b[bii] != c[aii+bii+1] && a[aii] != c[aii+bii+1]) return false;
          bool ra=false, rb=false;
          if (a[aii] == c[aii+bii+1]) ra= build(a,b,c,aii-1,bii);
          if (b[bii] == c[aii+bii+1]) rb= build(a,b,c,aii,bii-1);
          return ra||rb;
        }
public:
    bool isInterleave(string s1, string s2, string s3) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s1.length() + s2.length() != s3.length()) return false;
        if (s1.empty() || s2.empty()) return (!s1.compare(s3) || !s2.compare(s3));
        return build(s1,s2,s3,s1.length()-1,s2.length()-1);
    }
};

/**The one below works for both small and large cases
*/
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s1.length() + s2.length() != s3.length()) return false;
        if (s1.empty() || s2.empty()) return (!s1.compare(s3) || !s2.compare(s3));

        s1 = "S"+s1;
        s2 = "S"+s2;
        s3 = "S"+s3;//index starts from 1
        vector<vector<bool> > v(s1.length()+1, vector<bool>(s2.length()+1, false));
        v[0][0]=true;
        for(int ii = 1; ii < s2.length(); ++ii){
            if (s2[ii] == s3[ii]) v[0][ii] = v[0][ii-1];
        }
        for(int ii = 1; ii < s1.length(); ++ii){
            if (s1[ii] == s3[ii]) v[ii][0] = v[ii-1][0];
        }
        for(int ii = 1; ii <s1.length(); ++ii){
            for(int jj = 1; jj <s2.length(); ++jj){
                if (s1[ii] == s3[ii+jj]) v[ii][jj] = v[ii][jj] || v[ii-1][jj];
                if (s2[jj] == s3[ii+jj]) v[ii][jj] = v[ii][jj] || v[ii][jj-1];
            }
        }
        return v[s1.length()-1][s2.length()-1];
    }
};