[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;
    }
};