Entering edit mode

Wildcard Matching

Click here to Practice

Submit Problem to OJ

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

- '?' Matches any single character.
- '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

**Constraints:**

- 0 <= s.length, p.length <= 2000
- s contains only lowercase English letters.
- p contains only lowercase English letters, '?' or '*'.

**Examples:**

**Input 1:**

s = "aa", p = "a"

**Output 1:**

false

**Explanation:**

"a" does not match the entire string "aa".

**Example 2:**

**Input 2:**

s = "aa", p = "*"

**Output 2:**

true

**Explanation:**

'*' matches any sequence.

**Input 3:**

s = "cb", p = "?a"

**Output 3:**

false

**Explanation:**

'?' matches 'c', but the second letter is 'a', which does not match 'b'.

Click here to Practice

Submit Problem to OJ

Given an integer array nums, find the subarray which has the largest sum and return its sum.

**Constraints:**

- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4

**Examples:**

**Input 1:**

nums = [-2,1,-3,4,-1,2,1,-5,4]

**Output:**

6

**Explanation:**

[4,-1,2,1] has the largest sum = 6.

**Input 2:**

nums = [1]

**Output 2:**

1

**Input 3:**

nums = [5,4,-1,7,8]

**Output 3:**

23

Click here to Practice

Submit Problem to OJ

Given two binary trees, you have to overlap Tree 2 over Tree 1.

**Example**

Tree 1: 4, 5, 6, 1, Null, 4, Null

Tree 2: 7, -2, -6, Null, 5, 4, 3

**Output:**

7, -2, -6, 1, -5, 4 ,3

**Shifting Homes**

Click here to Practice

Submit Problem to OJ

Homes are aligned in a row. In any given row, maximum half of the homes are occupied. In a season, people got infected and all must vacate homes to move to unoccupied homes. Movements are sequential and not parallel (i.e one home completes the movement, then only the second home starts). To reduce the overall time taken, it's better to move to a nearby empty room than a farther one. i'th home to j'th home movement results in abs(j-i) distance. Minimize the overall distance covered by the time all infected home completes the movement to unoccupied homes.

Input : n = no of homes String s denoting occupied and unoccupied homes(1 = occupied, 0 = unoccupied)

**Example:**

**Input**

n = 4

"1001"

**Output:**

2

A string S of length N has to be reconstructed from 2(start, end)+k substrings(random length). Start substring is a prefix of S and end substring is a suffix of S. These substrings can be overlapping each other from right, left or both sides with minimum of 4 characters.

**Example:**

**Input**

abcde123, de123xyz, 3xyzpqr

**Output :**

abcde123xyzpqr

Click here to Practice

Submit Problem to OJ

There are n balloons and n bullets and each balloon is assigned with a particular number (point).

Whenever a particular balloon is shot the no of points increases by

- The multiplication of point assigned to balloon on left and that of right side.
- Point assigned to left if no right exists
- Point assigned to right if no left exists.
- The point assigned to itself if no other balloon exists.

You have to output the maximum no of points possible.

**Input**

```
1 2 3 4
```

**Output**

```
20
```

Entering edit mode

This is a standard problem, usually done by Kadane's algorithm.

Following are the steps for Kadane's algorithm:

- Initialise a maxSoFar to -infinity and currentMax to 0
- maxSoFar contains answer till now, and currentMax is the sum for the current subarray
- Iterate over the array, add ai to currentMax
- If currentMax > maxSoFar, maxSoFar=currentMax
- If currentMax < 0 , we don't need to take the previous subarray, hence set currentMax = 0.

```
int maxSubarraySum(vector<int> a)
{
int n=a.size();
int maxSoFar=-1e9,maxEndingHere=0;
for(int i = 0;i < n;i++)
{
maxEndingHere=maxEndingHere+a[i];
maxSoFar=max(maxSoFar,maxEndingHere);
maxEndingHere=max(maxEndingHere,0ll);
}
return maxSoFar;
}
```

Entering edit mode

This is a well known dynamic programming problem which uses the idea of string matching DP.

- Let dp(i,j) = true if sub-string s[ i...n-1] matches with sub-pattern p[ j...m-1] , else false.
- We can define a recursive relation to find solution for this state using other precomputed states.
- dp(i,j) is true if any of the following below cases satisfies.
- Case 1 : if s[i] == p[j] , then dp(i,j) will be surely true if dp(i+1,j+1) is true.
- Case 2 : if p[j] == '?' , then dp(i,j) will be surely true if dp(i+1,j+1) is true.
- Case 3 : if p[j] == '*' , we have the following possibilities.
- Case 3.1 : Match current character and extend , check if dp(i+1,j) is true
- Case 3.2 : Match current character with '*' and end , check if dp(i+1,j+1) is true.
- Case 3.3 : Match zero characters , check if dp(i , j+1) is true
- Base cases:
- BC1 : If both pointers have reached the end. ( string has successfully matched with pattern)
- BC2 : if string pointer has reached the end , and pattern hasnt ended . (if remaining pattern contains only '*' , return true. Else false.)
- BC3 : pattern has ended , but string hasnt ended ( return false as this is an incomplete match )

```
string str , pat;
int dp[2001][2001];
int dfs(int i , int j){
//BASE CASE
if(i == str.size() && j == pat.size())return 1;
if(i == str.size() && j != pat.size()){
if(pat[j]=='*')return dp[i][j] = dfs(i , j+1);
else return dp[i][j] = 0;
}
if(i != str.size() && j == pat.size())return 0;
if(dp[i][j] != -1)return dp[i][j];
int val = 0;
// Case 1 : string matches with pattern , move both pointers ahead.
if(str[i] == pat[j])val |= dfs(i+1 , j+1);
// Case 2 : Match '?' with the string pointer , move both pointers ahead.
if(pat[j] == '?')val |= dfs(i+1 , j+1);
// Case 3 : Match '*' with zero or more string pointers.
if(pat[j] == '*'){
val |= dfs(i+1,j);
val |= dfs(i+1,j+1);
val |= dfs(i , j+1);
}
return dp[i][j] = val;
}
```

Entering edit mode

*Solution-Q3*

*Approach*

Step 1: Generate the binary trees from the input.

Step 2: Merge the binary trees.

- Traverse recursively.
- If subtree of Tree 2 is null, then node will be the subtree of Tree 1 as it is.
- If both the values exist, then value will be the value of Tree 2. Then traverse recursively in both the subtrees and repeat the procedure.

Step 3: Decompose the binary tree back into array format.

Here are the required function codes:

```
node* overlapTrees(node* r1, node* r2) {
if(r2 == nullptr)
return r1;
if(r1 == nullptr) {
return r2;
}
r2 -> left = overlapTrees(r1 -> left, r2 -> left);
r2 -> right = overlapTrees(r1 -> right, r2 -> right);
return r2;
}
vector <int> flattenTree(node* root) {
node* cur = root;
vector <int> tree;
queue <node*> q;
q.push(root);
if(cur != nullptr) {
tree.push_back(root -> val);
} else {
tree.push_back(0);
}
while(!q.empty()) {
if(cur -> left == nullptr && cur -> right == nullptr) {
q.pop();
continue;
}
if(cur -> left != nullptr) {
tree.push_back(cur -> left -> val);
q.push(cur -> left);
} else {
tree.push_back(0);
}
if(cur -> right != nullptr) {
tree.push_back(cur -> right -> val);
q.push(cur -> right);
} else {
tree.push_back(0);
}
q.pop();
if(!q.empty()) {
cur = q.front();
}
}
return tree;
}
node* tree_create(int* arr, int n){
queue <node*> q;
int i = 1;
bool l = true;
node* root = new node(arr[0]);
node* cur = root;
q.push(cur);
while(!q.empty() && i < n){
if(l) {
l ^= 1;
if(arr[i] != 0) {
cur -> left = new node(arr[i]);
q.push(cur -> left);
} else {
cur -> left = nullptr;
}
} else {
l ^= 1;
if(arr[i] != 0) {
cur -> right = new node(arr[i]);
q.push(cur -> right);
} else {
cur -> right = nullptr;
}
q.pop();
if(!q.empty()) {
cur = q.front();
}
}
i++;
}
return root;
}
```

Entering edit mode

**Question 4**

`overview:`

- N Houses are there in a line, of which m<=N/2 are occupied (denoted by 1) by a family
- All Families have to move to a house which was not occupied initially.
- Movements are sequential, only one family can move at a time.
- The time taken to move house number
`i`

to house number`j`

is equal to`abs(i-j)`

`Solution (O(N^2)):`

- Basic greedy idea: if family
`i1`

moves to`j1`

and family at family at`i2`

moves to`j2`

, and`i1 < i2`

, then`j1 < j2`

- There are only two possibilities
`j1`

is in between`i1`

and`i2`

, or`j1`

is after`i2`

- As the diagram below shows, in both cases
`j1 < j2`

gives a lower time'

- There are only two possibilities
- All arrays below are
`1 indexed`

- Now find the indices of houses with and without families and store them in array
`occupied[]`

and`empty[]`

respectively- Size of
`occupied[]`

=`K`

`occupied[i]`

= index of 'i^th' occupied house

- Size of
`empty[]`

=`L`

`empty[ij`

= index of 'j^th' empty house

- Size of
- Find distance between every empty and occupied house , store it in
`dist[][]`

`Dist[i][j]`

= Distance between`i^th`

occupied house and`j^th`

empty house .- Size of
`Dist[][]`

=`K*L`

- Define
`dp[i][j]`

= minimum time taken for movement of all families residing till`i^th`

occupied house to a empty house such that family on the`i^th`

occupied house moves to a empty house on or before`j^th`

empty house`Initialization:`

- all
`dp[i][j] = INF`

`dp[1][1] = dist[1][1]`

`dp[1][j] = min(dp[1][j-1],dist[1][j])`

- all
`Updation:`

`dp[i][j] = min(dp[i][j-1],dp[i-1][j-1]+dist[i][j])`

`final answer:`

- ANS = min of all
`dp[K][i]`

,`1 <= i <= L`

- ANS = min of all

Loading Similar Posts