# 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: