[C++] Data structures and their common operators

	vector	stack	queue	Deque (Double ended queue)	Priority_queue
Access	x=v.front() x=v.back()	x=s.top()	x=q.front()	x=dq.front() x=dq.back()	x=pq.top()
Add	v.insert(itr, x) v.push_back(x) v.emplace(itr, x) v.emplace_back(x)	s.emplace(x) s.push(x)	q.emplace(x) q.push(x)	dq.emplace(itr, x) dq.emplace_back(x) dq.emplace_front(x) dq.push_back(x) dq.push_front(x) dq.insert(itr,x)	pq.emplace(x) pq.push(x)
Remove	v.clear() v.erase(itr) v.pop_back()	s.pop()	q.pop()	dq.clear() dq.erase(itr) dq.pop_back() dq.pop_front()	pq.pop()
Check empty	v.empty()	s.empty()	q.empty()	dq.empty()	pq.empty()
Check size	x=v.size()	x=s.size()	x=q.size()	dq.size()	pq.size()

Vector vs. Deque:

Both vector and deque provide a very similar interface, but internally they work in quite different ways: vector uses a single array that needs occasionally re-allocation for growth; deque has its elements scattered in different chunk of storage, with the container keeping the necessary information for direct accesses to any element in constant time - through iterators.

[LeetCode] Maximum Subarray

Problem Statement (link):

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Analysis:
Suppose we scan from left to right, each element could either be counted in the max-sum subarray, or not. If we use an array to store this information, we probably could solve the problem in O(n) time.

Thus, the idea is to use DP to solve the problem. Specifically, the DP array stores the maximum sum we have so far if we count the current element in. In addition, we use an integer to store the maximum sum we have so far.

Code:

class Solution {
public:
    int maxSubArray(int A[], int n) {
        if (n==0) return 0;
        int maxSum=INT_MIN; // max sum so far
        vector<int> dp(n+1);  // dp[i+1]: the maxSum of subarray which ends with A[i];
        dp[0]=0;
        for (int i=0; i<n; i++) {
            if (dp[i]<0) dp[i+1]=A[i];
            else dp[i+1]=dp[i]+A[i];
            maxSum=max(maxSum, dp[i+1]);
        }
        return maxSum;
    }
};

[LeetCode] Generate Parentheses

Problem Statement (link):

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

Analysis:
The problem asks for all combinations, this usually indicates it's a DFS problem.

In the recursion function, if we've used up all left and right parentheses, we push the formed string into result vector. Otherwise, we can add either left parentheses or right parentheses. The code for this problem is shown in Sol 1 below.

The extended version of this problem is that instead of only having parentheses, we are given n1 parentheses pairs, n2 bracket pairs, and n3 curly parentheses, and we are asked for the same thing - all combinations.

The idea is pretty similar to the simple version. The only difference is that we can do one of the following:
1) add left parentheses '(';
2) add left bracket '[';
3) add left curly parentheses '{';
4) add the right part, depending on the left situation, we choose either ')', ']', or '}'.

The code is shown in Sol 2 below.

Code:
Sol 1:

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        if (n<1) return res;
        dfs(res, "", "", n);
        return res;
    }
    void dfs(vector<string> &res, string left, string tmp, int n) {
        if (left.size()==0 && n==0) {
            res.push_back(tmp);
            return;
        }
        if (n>0) {
            dfs(res, "("+left, tmp+"(", n-1);
        }
        if (left.size()>0) {
            dfs(res, left.substr(1), tmp+")", n);
        }
    }
};

Sol 2:

string rightPart(string left) {
    if (left=="(") return ")";
    else if (left=="[") return "]";
    else return "}";
}

void dfsParen(vector<string> &res, string leftStack, string str, int n1, int n2, int n3) {
    if (leftStack.empty() && n1==0 && n2==0 && n3==0) {
        res.push_back(str);
        return;
    }

    // add left parentheses
    if (n1>0) {
        dfsParen(res, "("+leftStack, str+"(", n1-1, n2, n3);
    }
    if (n2>0) {
        dfsParen(res, "["+leftStack, str+"[", n1, n2-1, n3);
    }
    if (n3>0) {
        dfsParen(res, "{"+leftStack, str+"{", n1, n2, n3-1);
    }

    // add right parentheses
    if (!leftStack.empty()) {
        dfsParen(res, leftStack.substr(1), str+rightPart(leftStack.substr(0,1)), n1, n2, n3);
    }
}

vector<string> getParen(int n1, int n2, int n3) {
    vector<string> res;
    if (n1==0 && n2==0 && n3==0) return res;
    string leftStack;
    string str="";
    dfsParen(res, leftStack, str, n1, n2, n3);
    return res;
}

[LeetCode] Container with Most Water

Problem Statement (link):

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

Analysis:
The naive O(n^2) brute force is apparently not optimal.

An O(n) algorithm goes like this:
- Start from the very beginning and end of the vector, we calculate the volume hold by these two boards;
- Compare the height of current boards, advance the shorter board;

To justify this algorithm, think about the following case:
Suppose we are currently at left index i, right index j. If height i is smaller height j, then with any other height jj (i<jj<j), the area(i, jj) < area(i, j). The reason is that the container area is determined by the shorter height of the two boards, i.e., board i. In other words, the maximum area that determined by board i is already found.

Code:

class Solution {
public:
    int maxArea(vector<int> &height) {
        int left=0, right=height.size()-1;
        int vol=min(height[left], height[right]) * (right-left);
        while (left<right) {
            if (height[left]<height[right]) left++;
            else right--;
            vol=max(vol, min(height[left], height[right]) * (right-left));
        }
        return vol;
    }
};

[LeetCode] String to Integer (atoi)

Problem Statement (link):

Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Analysis:
The logic/algorithm is pretty simple, the tricky part is about all the corner cases..:
1) "+-2" --> "0", multiple sign appeared;
2) Once you met a char, you should return the current integer by discarding all the rest of the string. i.e., "-23a56" --> "-23" rather than "-2356";
3) Overflow.

O(n) time complexity is required as we need to scan all the chars.

Code:

class Solution {
public:
    int atoi(const char *str) {
        while(*str==' ') str++;
        int sign=1;
        if (*str=='-' || *str=='+') {
            if ((*str=='+'&&*(str+1)=='-')||(*str=='-'&&*(str+1)=='+'))
                return 0;
            sign=*str=='-'?-1:1; str++;
        }

        int res=0;
        while(*str) {
            if (!isDigit(*str)) break;
            res=10*res+(*str-'0');
            str++;
            // overflow
            if ((res>=214748364 && *str>='8' && *str<='9') || res>=999999999 && isDigit(*str))
                return sign==1?INT_MAX:INT_MIN;
        }
        return res*sign;
    }
    bool isDigit(const char c) {
        int d=c-'0';
        if (d>=0 && d<=9)
            return true;
        return false;
    }
};

[LeetCode] Reverse Integer

Problem Statement (link):

Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

Analysis:
There are several ways to approach this problem, we could convert the integer to string, inverse the string, then convert the string to int. Or, we could read each digit into a stack, pop out each digit in sequence and form a new integer.

Here, I simple extract each digit from the end of int x by taking the reminder. The time complexity is O(n) where n is the length of the integer.

Code:

class Solution {
public:
    int reverse(int x) {
        int sign=x<0?-1:1;
        x=abs(x);
        int rev=0;
        while (x>0) {
            rev=rev*10+x%10;
            x/=10;
            if (rev<0) return 0; // overflow
        }
        return rev*sign;
    }
};

[LeetCode] Interleaving String

Problem Statement (link):

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.

Analysis:
It reminds me of the Edit Distance problem. As we could break this problem down to some smaller problems, i.e., consider if s1[:i-1] and s2[:j-1] could build s[:i+j-1], we could use DP.

We could construct a matrix dp[s1.length()+1][s2.length()+1], remember in DP we usually leave one more extra space for initial condition, which is both s1 and s2 are blank string in this problem. Each entry dp[i][j] indicates whether s1[i-1] and s2[j-1] could build  s[:i+j-1].

Now consider the transfer function. dp[i][j] is true if either of the following cases is true:
1) current char in s1 is same as current char in s3, and previous dp entry in the same row is true
i.e., s1[i-1]==s3[i+j-1] && dp[i-1][j]) == true
2) current char in s2 is same as current char in s3, and previous dp entry in the same col is true
i.e., s2[j-1]==s3[i+j-1] && dp[i][j-1] == true

Our final answer is in the last entry of the DP matrix.

The time complexity of the algorithm is O(len1 * len2), where the two lengths are the lengths of s1 and s2, respectively.

Code:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int len1=s1.length(), len2=s2.length();
        if (len1+len2!=s3.length()) return false;
        vector<vector<bool>> dp(len1+1, vector<bool> (len2+1, false));

        // initial
        dp[0][0]=true;
        for (int i=1; i<=len1; i++)
            if (s1[i-1]==s3[i-1] && dp[i-1][0]) dp[i][0]=true;
        for (int j=1; j<=len2; j++)
            if (s2[j-1]==s3[j-1] && dp[0][j-1]) dp[0][j]=true;

        // update dp
        for (int i=1; i<=len1; i++) {
            for (int j=1; j<=len2; j++) {
                dp[i][j]=(s1[i-1]==s3[i+j-1] && dp[i-1][j]) || (s2[j-1]==s3[i+j-1] && dp[i][j-1]);
            }
        }
        return dp[len1][len2];
    }
};

[LeetCode] Scramble String

Problem Statement (link):

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Analysis:
The problem nicely defined the scramble string as a node-swapped binary tree. Thus, we want to check any two siblings that if they are swapped.

Consider base cases:
For any string pairs, if they are of different size or consisted of different sets of letters, they are not scramble string. Further:
- If two string are the same, they are scramble string

Consider the recursion. Suppose we have the following two trees:

    node1
   /    \
left1   right1

    node2
   /    \
left2   right2

we will need to check isScramble(left1, left2) && isScramble(right1, right2), or isScramble(left1, right2) && isScramble(right1, left2), make sure the two strings passed in are the same length, as different-length strings are guaranteed to be non-Scramble.

The time complexity of this recursive algorithm is pretty high though in exponential. It gets pass the OJ because the conditions that I check before going to recursions.

In the worst situation, for any recursion f(n), we will check all the combinations twice, i.e., f(n) = 2[f(1) + f(n-1)] +2[f(2) + f(n-2)] … + 2[f(n/2) + f(n/2+1)], thus, f(n+1)=3*f(n), we have f(n)=3^n.

Code:

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int len=s1.size();
        if (s1==s2) return true;
        if (s1.size()!=s2.size()) return false;
        int val1=0, val2=0;
        for (int i=0; i<len; i++) {
            val1+=s1[i]-'a';
            val2+=s2[i]-'a';
        }
        if (val1!=val2) return false;
       
        for (int i=1; i<len; i++) {
            string a1=s1.substr(0,i);
            string b1=s1.substr(i);
            string a2=s2.substr(0,i);
            string b2=s2.substr(i);
            if (isScramble(a1,a2)&&isScramble(b1,b2))
                return true;
            string a3=s2.substr(len-i);
            string b3=s2.substr(0,len-i);
            if (isScramble(a1,a3)&&isScramble(b1,b3))
                return true;
        }
        return false;
    }
};

[LeetCode] Wildcard Matching

Problem Statement (link):

Implement wildcard pattern matching with support for '?' and '*'.

'?' 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

Analysis:

The difficulty of this problem is how to deal with '*' as it may match None or 1 or more chars.

Suppose we use a variable to record the position of '*' in string p, and we temporarily skip to the next non-'*' char. If that char in string p matches a char in string s, life is good - meaning that we could match the '*' with either None or multiple chars in string s; otherwise, we proceed the pointer in string s to seek for a matching char.

An example worth a million words. Suppose we have:

s="abcde", p="?**e*"

- compare 'a' with '?' ==> match, advance both pointers s & p
- see a '*', use variable star to record the star location, advance p, use variable ss to record s's pointer
- see another '*', update both p and star. Now s-->'b', p-->'e'
- variable star is not empty, advance both p and ss (and s), until we meet 'e' in string s
- 'e' matches 'e', advance both pointers, and now *s=='\0', we jump out of the while loop
- Finally, skip all left '*'s from string p. If we reach end of string p, return true; otherwise, return false;

Code:

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        const char *star=NULL, *ss=s;
        while(*s!='\0') {
            if (*s==*p || *p=='?') {
                s++; p++; continue;
            }
            if (*p=='*') {
                star=p++; ss=s; continue;
            }
            if (star) {
                p=star+1; s=++ss; continue;
            }
            return false;
        }
        while (*p=='*') p++;
        return *p=='\0';
    }
};

[LeetCode] Substring with Concatenation of All Words

Problem Statement (link):

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).

Analysis:
The first solution I tried is to build a hash map that has all the combinations of words, so that we could have O(n/k) processing time afterwards, where n is the length of string S, and k is the length of a concatenated string. But I got MLE...

The second algorithm - see Sol 2 - , which is straightforward, got me an AC. Basically, we traverse the entire string S and check one word (NOT the concatenated long string!) at a time:
- if it matches our hash map, we check next word and so on;
- otherwise, we break immediately to check the word starts at next index

In the worst situation, where every time we check till the last word, we have O(n*m) time complexity, where n is the length of string S and m is the number of words in L.

Code:
Sol 1 - Memory Limit Exceed

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        unordered_set<string> comb; // store all combinations of L
        vector<int> res;
        string src="";
        for (int i=0; i<L.size(); i++) {
            src+=L[i];
        }

        // build up all permutations
        int match_len=L.size()*L[0].size();
        permute(comb, src, 0, match_len);

        // scan S
        for (int i=0; i<S.length(); i++) {
            if (i+match_len<S.length()) {
                string match_str=S.substr(i, match_len);
                if (comb.find(match_str)!=comb.end())
                    res.push_back(i);
            }
        }
        return res;
    }

    void permute(unordered_set<string> &comb, string &src, int st, int len) {
        if (st>=len-1) {
            comb.emplace(src);
            return;
        }
        for (int i=st; i<len; i+=3) {
            swap_words(src, st, i);
            permute(comb, src, st+3, len);
            swap_words(src, st, i);
        }
    }

    void swap_words(string &src, int a, int b) {
        string tmp_a=src.substr(a,3);
        string tmp_b=src.substr(b,3);
        for (int i=a; i<a+3; i++)
            src[i]=tmp_b[i-a];
        for (int i=b; i<b+3; i++)
            src[i]=tmp_a[i-b];
    }
};

Sol 2 - AC

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        vector<int> res;
        unordered_map<string,int> map;
        for (int i=0; i<L.size(); i++)
            map[L[i]]++;

        // scan S
        int len=L[0].size();
        int match_len=L.size()*len;
        if (S.size()<match_len)
            return res;
        for (int i=0; i<=S.size()-match_len; i++) {
            unordered_map<string, int> map2;
            int j=0;
            for (j=0; j<match_len; j+=len) {
                string sub=S.substr(i+j, len);
                if (map.find(sub)!=map.end()) {
                    map2[sub]++;
                    if (map2[sub]>map[sub])
                        break;
                }
                else // immediately end loop
                    break;
            }
            // check if two map are the same
            if (j==match_len) res.push_back(i);
        }
        return res;
    }
};

[LeetCode] Longest Common Prefix

Problem Statement (link):
Write a function to find the longest common prefix string amongst an array of strings.
Analysis:
Pretty straight-forward. Choose any string, and compare its prefix - with length from 1 to the string length - with all other strings.

The time complexity is O(k*n), where k is the length of the string we choose, and n is the number of strings.

Code:

class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
        int size = strs.size();
        string result = "";
        if (size==0) return result;
        if (size==1) return strs.front();
        if (strs[0].empty()) return result;
       
        int len = strs[0].length();    // The longest prefix cannot be longer than any string, so take 1st string
        for (int k = 1; k <= len; k++) {     // k - length of current prefix
            string pref = strs[0].substr(0, k);
            for (int i = 1; i < size; i++) {// check thru all the strings in the vector, i - current string
                if (strs[i].empty()) return result;
                string pref_curr = strs[i].substr(0, k);
                if (pref.compare(pref_curr) != 0)   return pref.substr(0, k-1);
                if (k==len && i==size-1) return pref;
            }
        }
    }
};

[LeetCode] Insert Interval

Problem Statement (link):

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Analysis:
We need to keep checking overlaps between the new interval and each intervals in the given vector. Given that the original vector is sorted on the start value, we have following three cases to deal with. See code below for specifics.

Code:

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> res;
        if (intervals.size()==0) {
            res.push_back(newInterval);
            return res;
        }
       
        for (int i=0; i<intervals.size(); i++) {
            if (newInterval.start>intervals[i].end)
                res.push_back(intervals[i]);
            else if (newInterval.end<intervals[i].start) {
                res.push_back(newInterval);
                newInterval=intervals[i];
            }
            else {
                newInterval.start=min(newInterval.start, intervals[i].start);
                newInterval.end=max(newInterval.end, intervals[i].end);
            }
        }
        res.push_back(newInterval);
        return res;
    }
};

[LeetCode] Merge Intervals

Problem Statement (link):

Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Analysis:
The idea is simple, we keep comparing the end value of the previous interval with the start value of the current interval. If the end is smaller than the start, we push the previous interval into our result vector; otherwise, we merge the two intervals into one.

The time complexity is O(n).

Code:

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    static bool cmpFunc(Interval a, Interval b) {
        return a.start<b.start;
    }

    vector<Interval> merge(vector<Interval> &intervals) {
        if (intervals.size()<2) return intervals;
        std::sort(intervals.begin(), intervals.end(), cmpFunc);
        vector<Interval> res;
        int cur=1, prev=0;
        int start=intervals[prev].start, end=intervals[prev].end;
        while(cur<intervals.size()) {
            if (intervals[cur].start>end) {
                Interval *intv=new Interval(start, end);
                res.push_back(*intv);
                prev=cur;
                start=intervals[prev].start;
                end=intervals[prev].end;
                cur++;
            }
            else {
                end=max(end, intervals[cur].end);
                cur++;
            }
        }
        // push_back the rest
        Interval *intv=new Interval(start, end);
        res.push_back(*intv);
        return res;
    }
};

[LeetCode] Surrounded Regions

Problem Statement (link):

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Analysis:
Rather than recording the 2D positions for any scanned 'O', a trick is to substitute any border 'O's with another character - here in the Code I use 'Y'. And scan the board again to change any rest 'O's to 'X's, and change 'Y's back to 'O's.

We start searching 'O' from the four borders. I tried DFS first, the OJ gives Runtime error on the 250x250 large board; In the Sol 2 below, I implement BFS instead, and passed all tests.

The time complexity is O(n^2), as in the worst case, we may need to scan the entire board.

Code:
1, DFS

class Solution {
public:
    // dfs - Runtime error on large board 250x250
    void dfs(vector<vector<char>> &board, int r, int c) {
        if (r<0||r>board.size()-1||c<0||c>board[0].size()-1||board[r][c]!='O')
            return;
        board[r][c]='Y';
        dfs(board, r-1, c);
        dfs(board, r+1, c);
        dfs(board, r, c-1);
        dfs(board, r, c+1);
    }
    void solve(vector<vector<char>> &board) {
        if (board.empty() || board.size()<3 || board[0].size()<3)
            return;
        int r=board.size();
        int c=board[0].size();
        // dfs from boundary to inside
        for (int i=0; i<c; i++) {
            if (board[0][i]=='O')
                dfs(board, 0, i);   // first row
            if (board[c-1][i]=='O')
                dfs(board, c-1, i); // last row
        }
        for (int i=0; i<board.size(); i++) {
            if (board[i][0]=='O')
                dfs(board, i, 0);   // first col
            if (board[i][c-1])
                dfs(board, i, c-1); // last col
        }
        // scan entire matrix and set values
        for (int i=0; i<board.size(); i++) {
            for (int j=0; j<board[0].size(); j++) {
                if (board[i][j]=='O')
                    board[i][j]='X';
                else if (board[i][j]=='Y')
                    board[i][j]='O';
            }
        }
    }
};

2, BFS

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if (board.empty() || board.size()<3 || board[0].size()<3)
            return;
        int r=board.size();
        int c=board[0].size();
        // queues to store row and col indices
        queue<int> qr;
        queue<int> qc;
        // start from boundary
        for (int i=0; i<c; i++) {
            if (board[0][i]=='O') { qr.push(0); qc.push(i); }
            if (board[r-1][i]=='O') { qr.push(r-1); qc.push(i); }
        }
        for (int i=0; i<r; i++) {
            if (board[i][0]=='O') { qr.push(i); qc.push(0); }
            if (board[i][c-1]=='O') { qr.push(i); qc.push(c-1); }
        }
        // BFS
        while (!qr.empty()) {
            int rt=qr.front(); qr.pop();
            int ct=qc.front(); qc.pop();
            board[rt][ct]='Y';
            if (rt-1>=0 && board[rt-1][ct]=='O') { qr.push(rt-1); qc.push(ct); } // go left
            if (rt+1<r && board[rt+1][ct]=='O') { qr.push(rt+1); qc.push(ct); } // go right
            if (ct-1>=0 && board[rt][ct-1]=='O') { qr.push(rt); qc.push(ct-1); } // go up
            if (ct+1<c && board[rt][ct+1]=='O') { qr.push(rt); qc.push(ct+1); } // go down
        }

        // scan entire matrix and set values
        for (int i=0; i<board.size(); i++) {
            for (int j=0; j<board[0].size(); j++) {
                if (board[i][j]=='O') board[i][j]='X';
                else if (board[i][j]=='Y') board[i][j]='O';
            }
        }
    }
};

[LeetCode] Evaluate Reverse Polish Notation

Problem Statement (link):

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Analysis:
Read the two examples and the wiki link given in the problem carefully, and you'll find the problem is straight-forward - we could use stack to solve it.

For instance, in the second example above, we keep pushing element into the stack once we meet the operator "/", we then pop out the top two elements in the stack, calculate the result, and push the result back to stack, and so on.

In general, the algorithm goes like this:
- If the entry is not operator, we push it into stack
- Otherwise, we pop out top 2 element and calculate the result, and push the result back to stack.

The time and space complexity is O(n).

Code:

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        if (tokens.empty())
            return 0;
        stack<int> st;
        for(int i=0; i<tokens.size(); i++) {
            if (tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/") {
                int n1=st.top();
                st.pop();
                int n2=st.top();
                st.pop();
                int res=evaluate(n2, n1, tokens[i].c_str());
                st.push(res);
            }
            else {
                st.push(atoi(tokens[i].c_str()));
            }
        }
        return st.top();
    }
    int evaluate(int n1, int n2, const char* op) {
        int res;
        switch (*op) {
            case '+':
                res=n1+n2;
                break;
            case '-':
                res=n1-n2;
                break;
            case '*':
                res=n1*n2;
                break;
            case '/':
                res=n1/n2;
                break;
            default:
                break;
        }
        return res;
    }
};

[LeetCode] Longest Valid Parentheses

Problem Statement (link):

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Analysis:
Stack should be the first thought when we are asked about parentheses validation problem, as we could push the '(' and match it with any ')' we meet in the future.

However, the stack algorithm for this problem is not straight-forward. The reason is simple, as the problem allows any kind of parentheses combination; while the conventional stack algorithm requires consecutive validness.

Let's not abandon the conventional stack idea, i.e., push when meet '(', pop when meet ')'. Additionally, suppose we use a start variable to record the index of the latest possible start of a valid sequence:
- First, after a sequential push() operation, if the stack is empty, it implies so far we only see ')'. Thus we need to keep updating start variable to indicate the start of possible valid sequence shouldn't include any previous ')'s;
- Next, if we meet some ')' and pop() them out, we want to keep updating maxLen. However, there are two situations:
1) the stack is empty after we pop() something. For instance, s = " ( ) ", after we pop() the ')', the stack should be empty and we need to update the maxLen. If we have start indicating the possible start of a valid sequence, start = -1 (which is also the initial value), current valid length = i - start. And we update maxLen by taking the max between current valid length and previous possible maxLen.
2) the stack is not empty after we pop() something. For instance, s = ' ( ( ) ', after we pop the ')', the stack is not empty, and we also need to update the maxLen. Now, current valid length = 2, which is actually i - index of the first '(', the index of the first '(' could be obtained from peeking the top of the stack - as the stack is not empty right now, i.e., current valid length = i - stack.top(). Now, we get the idea that all the indices that are still in stack indicate the indices of the "invalid/unused" '('.

It's a bit difficult to get the idea of recording the valid length, working through an example would help.

Furthermore, the time complexity and worst space complexity is O(n), where n is length of the string.

Code:

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxLen=0;
        int start=-1;    // the possible start of a valid seq
        stack<int> st;  // save the index of '('
        for (int i=0; i<s.length(); i++) {
            if (s[i]=='(') {
                st.push(i);
            }
            else {
                if (st.empty()) {
                    start=i;
                }
                else {
                    st.pop();
                    if (st.empty()) {
                        maxLen=max(maxLen, i-start);
                    }
                    else {
                        maxLen=max(maxLen, i-st.top());
                    }
                }
            }
        }
        return maxLen;
    }
};

[LeetCode] Palindrome Number

Problem Statement (link):

Determine whether an integer is a palindrome. Do this without extra space.
Some hints:
Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
There is a more generic way of solving this problem.

Analysis:
The hints rule some straightforward ideas you may get.

Generically, we would look at the first (MSB) and the last digit (LSB) of an integer to determine if it's palindrome, then move on to the second MSB and second LSB, and so on... We could implement this method directly.

In the following method, I remove the MSB and LSB each time I compare them, so that every time I only need to look at the MSB and LSB of the updated integer.

Code:

class Solution {
public:
    bool isPalindrome(int x) {
        if (x<0) return false;
        // get num length
        int len=1, t=x;
        while(t/10>=1) {
            t/=10;
            len++;
        }

        // compare first and last digit
        while(x>0) {
            int d=pow(10,len-1);
            if (x%10!=x/d)
                return false;
            int t=x%d;
            x=(t-t%10)/10;
            len-=2;
        }

        return true;
    }
};