087. Scramble String

Difficulty: Hard

Frequency: N/A

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.

---

Test Cases:

---

Solution 1:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Code:

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int n1 = s1.size(), n2 = s2.size();
        if (n1 != n2) return false;
        vector<int> sums(26, 0);
        for (int i = 0; i < n1; i++) sums[s1[i] - 'a']++;
        for (int i = 0; i < n2; i++) sums[s2[i] - 'a']--;
        for (int i = 0; i < sums.size(); i++) {
            if (sums[i] != 0) return false;
        }
        if (n1 == 1) return true;
        for (int i = 1; i < n1; i++) {
            bool result = isScramble(s1.substr(0, i), s2.substr(0, i)) &&
                isScramble(s1.substr(i, n1 - i), s2.substr(i, n1 - i));
            result = result || isScramble(s1.substr(0, i), s2.substr(n1 - i, i)) &&
                isScramble(s1.substr(i, n1 - i), s2.substr(0, n1 - i));
            if (result) return true;
        }
        return false;
    }
};

---

Solution 2:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Submission errors:

 

---

Things to learn:

085. Maximal Rectangle

Difficulty: Hard

Frequency: N/A

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

---

Test Cases:

---

Solution 1:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Code:

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector<int> left(n, 0), right(n, n), height(n, 0);
        int maxA = 0;
        for (int i = 0; i < m; i++) {
            int cur_left = 0, cur_right = n;
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') height[j]++;
                else height[j] = 0;
            }
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') left[j] = max(left[j], cur_left);
                else {
                    cur_left = j + 1;
                    left[j] = 0;
                }
            }
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') right[j] = min(right[j], cur_right);
                else {
                    cur_right = j;
                    right[j] = n;
                }
            }
            for (int j = 0; j < n; j++) {
                maxA = max(maxA, (right[j] - left[j]) * height[j]);
            }
        }
        return maxA;
    }
};

---

Solution 2:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Submission errors:

 

---

Things to learn:

072. Edit Distance

Difficulty: Hard

Frequency: N/A

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

---

Test Cases:

---

Solution 1:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Code:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j - 1];
                if (word1[i - 1] != word2[j - 1]) dp[i][j]++;
                dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i][j]);
            }
        }
        return dp[m][n];
    }
};

---

Solution 2:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Submission errors:

 

---

Things to learn:

044. Wildcard Matching

Difficulty: Hard

Frequency: N/A

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

---

Test Cases:

---

Solution 1:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Code:

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        int i = 0, j = 0, asterick = -1, match;
        while (i < m) {
            if (j < n && (s[i] == p[j] || p[j] == '?')) {
                i++;
                j++;
            } else if (j < n && p[j] == '*') {
                match = i;
                asterick = j++;
            } else if (asterick >= 0) {
                i = ++match;
                j = asterick + 1;
            } else return false;
        }
        while(j < n && p[j] == '*') j++;
        return n == j;
    }
};

---

Solution 2:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Submission errors:

 

---

Things to learn:

032. Longest Valid Parentheses

Difficulty: Hard

Frequency: N/A

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.

---

Test Cases:

---

Solution 1:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Code:

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        if (n <= 1) return 0;
        vector<int> dp(s.size(), 0);
        int maxL = 0;
        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2;
                    maxL = max(maxL, dp[i]);
                } else {
                    if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
                        dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
                        maxL = max(maxL, dp[i]);
                    }
                }
            }
        }
        return maxL;
    }
};

---

Solution 2:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Submission errors:

 

---

Things to learn:

322. Coin Change

Difficulty: Medium

Frequency: N/A

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

---

Test Cases:

---

Solution 1:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Code:

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, -1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int c : coins) {
                if (i - c >= 0 && dp[i - c] != -1) {
                    dp[i] = dp[i] > 0 ? min(dp[i], dp[i - c] + 1) : dp[i - c] + 1;
                }
            }
        }
        return dp[amount];
    }
};

---

Solution 2:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Submission errors:

 

---

Things to learn:

309. Best Time to Buy and Sell Stock with Cooldown

Difficulty: Medium

Frequency: N/A

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

• You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

---

Test Cases:

---

Solution 1:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Code:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = INT_MIN, sell = 0, coolDown = 0, noOp = INT_MIN;
        for (int p : prices) {
            noOp = max(buy, noOp);
            buy = coolDown - p;
            coolDown = max(sell, coolDown);
            sell = noOp + p;
        }
        return max(sell, coolDown);
    }
};

---

Solution 2:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Submission errors:

 

---

Things to learn:

300. Longest Increasing Subsequence

Difficulty: Medium

Frequency: N/A

 

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n²) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

---

Test Cases:

---

Solution 1:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Code:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (!n) return 0;
        int result = 0;
        vector<int> dp(n, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
            }
            result = max(result, dp[i]);
        }
        return result;
    }
};

---

Solution 2:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Submission errors:

 

---

Things to learn:

304. Range Sum Query 2D – Immutable

Difficulty: Medium

Frequency: N/A

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

Note:

1. You may assume that the matrix does not change.
2. There are many calls to sumRegion function.
3. You may assume that row1 ≤ row2 and col1 ≤ col2.

---

Test Cases:

---

Solution 1:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Code:

class NumMatrix {
private:
    vector<vector<int>> sums;
public:
    NumMatrix(vector<vector<int>> &matrix) {
        int m = matrix.size();
        int n = m > 0 ? matrix[0].size() : 0;
        sums = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sums[i][j] = matrix[i - 1][j - 1] + sums[i][j - 1] + sums[i - 1][j] - sums[i - 1][j - 1];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row2 + 1][col1] - sums[row1][col2 + 1] + sums[row1][col1];
    }
};


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);

---

Solution 2:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Submission errors:

 

---

Things to learn:

256. (Locked)Paint House

Difficulty: Medium

Frequency: N/A

 

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red;costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

---

Test Cases:

---

Solution 1:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Code:

---

Solution 2:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        if (costs.empty()) return 0;
        int n = costs.size(), r = 0, g = 0, b = 0;
        for (int i = 0; i < n; i++) {
            int pr = r, pg = g, pb = b;
            r = min(pg, pb) + costs[i][0];
            g = min(pr, pb) + costs[i][1];
            b = min(pr, pg) + costs[i][2];
        }
        return min(min(r, g), b);
    }
};

---

Submission errors:

 

---

Things to learn: