Problem list:

- Remove Outermost Parentheses
- Sum of Root To Leaf Binary Numbers
- Camelcase Matching
- Video Stitching

This week, I solved the first 3 questions.

## 1021. Remove Outermost Parentheses

### Problem

A valid parentheses string is either empty `("")`

, `"(" + A + ")"`

, or `A + B`

, where `A`

and `B`

are valid parentheses strings, and `+`

represents string concatenation. For example, `""`

, `"()"`

, `"(())()"`

, and `"(()(()))"`

are all valid parentheses strings.

A valid parentheses string `S`

is **primitive** if it is nonempty, and there does not exist a way to split it into `S = A+B`

, with `A`

and `B`

nonempty valid parentheses strings.

Given a valid parentheses string `S`

, consider its primitive decomposition: `S = P_1 + P_2 + ... + P_k`

, where `P_i`

are primitive valid parentheses strings.

Return `S`

after removing the outermost parentheses of every primitive string in the primitive decomposition of `S`

.

**Example 1:**

1 | Input: "(()())(())" |

**Example 2:**

1 | Input: "(()())(())(()(()))" |

**Example 3:**

1 | Input: "()()" |

**Note:**

`S.length <= 10000`

`S[i]`

is`"("`

or`")"`

`S`

is a valid parentheses string

https://leetcode.com/contest/weekly-contest-131/problems/remove-outermost-parentheses/

### Solution

I was first considering using a stack for this question. But then I found that a boolean is enough to solve this.

The idea is when iterating the given input, store the usable (i.e. not "outer") parentheses by filtering the outer ones. To recognise the outer ones, I use a boolean `hasOuter`

to switch between the states whether there's an left-side outer parentheses `(`

waiting for the right-side one or not.

1 | class Solution { |

## 1022. Sum of Root To Leaf Binary Numbers

### Problem

Given a binary tree, each node has value `0`

or `1`

. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is `0 -> 1 -> 1 -> 0 -> 1`

, then this could represent `01101`

in binary, which is `13`

.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf.

Return the sum of these numbers.

**Example 1:**

1 | Input: [1,0,1,0,1,0,1] |

**Note:**

- The number of nodes in the tree is between
`1`

and`1000`

. - node.val is
`0`

or`1`

. - The answer will not exceed
`2^31 - 1`

.

https://leetcode.com/contest/weekly-contest-131/problems/sum-of-root-to-leaf-binary-numbers/

### Solution

My idea is quite straightforward: use recursive solution.

1 | /** |

Pay attention to avoiding overflow of integers.

## 1023. Camelcase Matching

### Problem

A query word matches a given `pattern`

if we can insert **lowercase** letters to the pattern word so that it equals the `query`

. (We may insert each character at any position, and may insert 0 characters.)

Given a list of `queries`

, and a `pattern`

, return an `answer`

list of booleans, where `answer[i]`

is true if and only if `queries[i]`

matches the `pattern`

.

**Example 1:**

1 | Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB" |

**Example 2:**

1 | Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa" |

**Example 3:**

1 | Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBaT" |

**Note:**

`1 <= queries.length <= 100`

`1 <= queries[i].length <= 100`

`1 <= pattern.length <= 100`

- All strings consists only of lower and upper case English letters.

https://leetcode.com/contest/weekly-contest-131/problems/camelcase-matching/

### Solution

For each query, for each character, if it equals to the next unchecked pattern character, increase counter `checked`

by `1`

, otherwise if it's also an upper case, loop out and mark this query `false`

. If the loop finishes with `checked`

equal to the length of pattern, mark this query `true`

.

1 | class Solution { |

The variable `isMatched`

could also be removed:

1 | class Solution { |

## 1024. Video Stitching

### Problem

You are given a series of video clips from a sporting event that lasted `T`

seconds. These video clips can be overlapping with each other and have varied lengths.

Each video clip `clips[i]`

is an interval: it starts at time `clips[i][0]`

and ends at time `clips[i][1]`

. We can cut these clips into segments freely: for example, a clip `[0, 7]`

can be cut into segments `[0, 1] + [1, 3] + [3, 7]`

.

Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event (`[0, T]`

). If the task is impossible, return `-1`

.

**Example 1:**

1 | Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10 |

**Example 2:**

1 | Input: clips = [[0,1],[1,2]], T = 5 |

**Example 3:**

1 | Input: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9 |

**Example 4:**

1 | Input: clips = [[0,4],[2,8]], T = 5 |

**Note:**

`1 <= clips.length <= 100`

`0 <= clips[i][0], clips[i][1] <= 100`

`0 <= T <= 100`

### Solution

1 |