bowang0911/leetcode huggingface dataset:
Most Profit Assigning Work

You have `n` jobs and `m` workers. You are given three arrays: `difficulty`, `profit`, and `worker` where:

*   `difficulty[i]` and `profit[i]` are the difficulty and the profit of the `ith` job, and
*   `worker[j]` is the ability of `jth` worker (i.e., the `jth` worker can only complete a job with difficulty at most `worker[j]`).

Every worker can be assigned **at most one job**, but one job can be **completed multiple times**.

*   For example, if three workers attempt the same job that pays `$1`, then the total profit will be `$3`. If a worker cannot complete any job, their profit is `$0`.

Return the maximum profit we can achieve after assigning the workers to the jobs.

**Example 1:**

**Input:** difficulty = \[2,4,6,8,10\], profit = \[10,20,30,40,50\], worker = \[4,5,6,7\]
**Output:** 100
**Explanation:** Workers are assigned jobs of difficulty \[4,4,6,6\] and they get a profit of \[20,20,30,30\] separately.

**Example 2:**

**Input:** difficulty = \[85,47,57\], profit = \[24,66,99\], worker = \[40,25,25\]
**Output:** 0

**Constraints:**

*   `n == difficulty.length`
*   `n == profit.length`
*   `m == worker.length`
*   `1 <= n, m <= 104`
*   `1 <= difficulty[i], profit[i], worker[i] <= 105`
Making A Large Island

You are given an `n x n` binary matrix `grid`. You are allowed to change **at most one** `0` to be `1`.

Return _the size of the largest **island** in_ `grid` _after applying this operation_.

An **island** is a 4-directionally connected group of `1`s.

**Example 1:**

**Input:** grid = \[\[1,0\],\[0,1\]\]
**Output:** 3
**Explanation:** Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

**Example 2:**

**Input:** grid = \[\[1,1\],\[1,0\]\]
**Output:** 4
**Explanation:** Change the 0 to 1 and make the island bigger, only one island with area = 4.

**Example 3:**

**Input:** grid = \[\[1,1\],\[1,1\]\]
**Output:** 4
**Explanation:** Can't change any 0 to 1, only one island with area = 4.

**Constraints:**

*   `n == grid.length`
*   `n == grid[i].length`
*   `1 <= n <= 500`
*   `grid[i][j]` is either `0` or `1`.
Count Unique Characters of All Substrings of a Given String

Let's define a function `countUniqueChars(s)` that returns the number of unique characters on `s`.

*   For example, calling `countUniqueChars(s)` if `s = "LEETCODE "` then `"L "`, `"T "`, `"C "`, `"O "`, `"D "` are the unique characters since they appear only once in `s`, therefore `countUniqueChars(s) = 5`.

Given a string `s`, return the sum of `countUniqueChars(t)` where `t` is a substring of `s`. The test cases are generated such that the answer fits in a 32-bit integer.

Notice that some substrings can be repeated so in this case you have to count the repeated ones too.

**Example 1:**

**Input:** s =  "ABC "
**Output:** 10
**Explanation:** All possible substrings are:  "A ", "B ", "C ", "AB ", "BC " and  "ABC ".
Every substring is composed with only unique letters.
Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10

**Example 2:**

**Input:** s =  "ABA "
**Output:** 8
**Explanation:** The same as example 1, except `countUniqueChars`( "ABA ") = 1.

**Example 3:**

**Input:** s =  "LEETCODE "
**Output:** 92

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` consists of uppercase English letters only.
Consecutive Numbers Sum

Given an integer `n`, return _the number of ways you can write_ `n` _as the sum of consecutive positive integers._

**Example 1:**

**Input:** n = 5
**Output:** 2
**Explanation:** 5 = 2 + 3

**Example 2:**

**Input:** n = 9
**Output:** 3
**Explanation:** 9 = 4 + 5 = 2 + 3 + 4

**Example 3:**

**Input:** n = 15
**Output:** 4
**Explanation:** 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

**Constraints:**

*   `1 <= n <= 109`
Positions of Large Groups

In a string `s` of lowercase letters, these letters form consecutive groups of the same character.

For example, a string like `s = "abbxxxxzyy "` has the groups `"a "`, `"bb "`, `"xxxx "`, `"z "`, and `"yy "`.

A group is identified by an interval `[start, end]`, where `start` and `end` denote the start and end indices (inclusive) of the group. In the above example, `"xxxx "` has the interval `[3,6]`.

A group is considered **large** if it has 3 or more characters.

Return _the intervals of every **large** group sorted in **increasing order by start index**_.

**Example 1:**

**Input:** s =  "abbxxxxzzy "
**Output:** \[\[3,6\]\]
**Explanation:** `"xxxx " is the only` large group with start index 3 and end index 6.

**Example 2:**

**Input:** s =  "abc "
**Output:** \[\]
**Explanation:** We have groups  "a ",  "b ", and  "c ", none of which are large groups.

**Example 3:**

**Input:** s =  "abcdddeeeeaabbbcd "
**Output:** \[\[3,5\],\[6,9\],\[12,14\]\]
**Explanation:** The large groups are  "ddd ",  "eeee ", and  "bbb ".

**Constraints:**

*   `1 <= s.length <= 1000`
*   `s` contains lowercase English letters only.
Masking Personal Information

You are given a personal information string `s`, representing either an **email address** or a **phone number**. Return _the **masked** personal information using the below rules_.

**Email address:**

An email address is:

*   A **name** consisting of uppercase and lowercase English letters, followed by
*   The `'@'` symbol, followed by
*   The **domain** consisting of uppercase and lowercase English letters with a dot `'.'` somewhere in the middle (not the first or last character).

To mask an email:

*   The uppercase letters in the **name** and **domain** must be converted to lowercase letters.
*   The middle letters of the **name** (i.e., all but the first and last letters) must be replaced by 5 asterisks `"***** "`.

**Phone number:**

A phone number is formatted as follows:

*   The phone number contains 10-13 digits.
*   The last 10 digits make up the **local number**.
*   The remaining 0-3 digits, in the beginning, make up the **country code**.
*   **Separation characters** from the set `{'+', '-', '(', ')', ' '}` separate the above digits in some way.

To mask a phone number:

*   Remove all **separation characters**.
*   The masked phone number should have the form:
    *   `"***-***-XXXX "` if the country code has 0 digits.
    *   `"+*-***-***-XXXX "` if the country code has 1 digit.
    *   `"+**-***-***-XXXX "` if the country code has 2 digits.
    *   `"+***-***-***-XXXX "` if the country code has 3 digits.
*   `"XXXX "` is the last 4 digits of the **local number**.

**Example 1:**

**Input:** s =  "LeetCode@LeetCode.com "
**Output:**  "l\*\*\*\*\*e@leetcode.com "
**Explanation:** s is an email address.
The name and domain are converted to lowercase, and the middle of the name is replaced by 5 asterisks.

**Example 2:**

**Input:** s =  "AB@qq.com "
**Output:**  "a\*\*\*\*\*b@qq.com "
**Explanation:** s is an email address.
The name and domain are converted to lowercase, and the middle of the name is replaced by 5 asterisks.
Note that even though  "ab " is 2 characters, it still must have 5 asterisks in the middle.

**Example 3:**

**Input:** s =  "1(234)567-890 "
**Output:**  "\*\*\*-\*\*\*-7890 "
**Explanation:** s is a phone number.
There are 10 digits, so the local number is 10 digits and the country code is 0 digits.
Thus, the resulting masked number is  "\*\*\*-\*\*\*-7890 ".

**Constraints:**

*   `s` is either a **valid** email or a phone number.
*   If `s` is an email:
    *   `8 <= s.length <= 40`
    *   `s` consists of uppercase and lowercase English letters and exactly one `'@'` symbol and `'.'` symbol.
*   If `s` is a phone number:
    *   `10 <= s.length <= 20`
    *   `s` consists of digits, spaces, and the symbols `'('`, `')'`, `'-'`, and `'+'`.
Flipping an Image

Given an `n x n` binary matrix `image`, flip the image **horizontally**, then invert it, and return _the resulting image_.

To flip an image horizontally means that each row of the image is reversed.

*   For example, flipping `[1,1,0]` horizontally results in `[0,1,1]`.

To invert an image means that each `0` is replaced by `1`, and each `1` is replaced by `0`.

*   For example, inverting `[0,1,1]` results in `[1,0,0]`.

**Example 1:**

**Input:** image = \[\[1,1,0\],\[1,0,1\],\[0,0,0\]\]
**Output:** \[\[1,0,0\],\[0,1,0\],\[1,1,1\]\]
**Explanation:** First reverse each row: \[\[0,1,1\],\[1,0,1\],\[0,0,0\]\].
Then, invert the image: \[\[1,0,0\],\[0,1,0\],\[1,1,1\]\]

**Example 2:**

**Input:** image = \[\[1,1,0,0\],\[1,0,0,1\],\[0,1,1,1\],\[1,0,1,0\]\]
**Output:** \[\[1,1,0,0\],\[0,1,1,0\],\[0,0,0,1\],\[1,0,1,0\]\]
**Explanation:** First reverse each row: \[\[0,0,1,1\],\[1,0,0,1\],\[1,1,1,0\],\[0,1,0,1\]\].
Then invert the image: \[\[1,1,0,0\],\[0,1,1,0\],\[0,0,0,1\],\[1,0,1,0\]\]

**Constraints:**

*   `n == image.length`
*   `n == image[i].length`
*   `1 <= n <= 20`
*   `images[i][j]` is either `0` or `1`.
Find And Replace in String

You are given a **0-indexed** string `s` that you must perform `k` replacement operations on. The replacement operations are given as three **0-indexed** parallel arrays, `indices`, `sources`, and `targets`, all of length `k`.

To complete the `ith` replacement operation:

1.  Check if the **substring** `sources[i]` occurs at index `indices[i]` in the **original string** `s`.
2.  If it does not occur, **do nothing**.
3.  Otherwise if it does occur, **replace** that substring with `targets[i]`.

For example, if `s = "abcd "`, `indices[i] = 0`, `sources[i] = "ab "`, and `targets[i] = "eee "`, then the result of this replacement will be `"eeecd "`.

All replacement operations must occur **simultaneously**, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will **not overlap**.

*   For example, a testcase with `s = "abc "`, `indices = [0, 1]`, and `sources = [ "ab ", "bc "]` will not be generated because the `"ab "` and `"bc "` replacements overlap.

Return _the **resulting string** after performing all replacement operations on_ `s`.

A **substring** is a contiguous sequence of characters in a string.

**Example 1:**

**Input:** s =  "abcd ", indices = \[0, 2\], sources = \[ "a ",  "cd "\], targets = \[ "eee ",  "ffff "\]
**Output:**  "eeebffff "
**Explanation:**
 "a " occurs at index 0 in s, so we replace it with  "eee ".
 "cd " occurs at index 2 in s, so we replace it with  "ffff ".

**Example 2:**

**Input:** s =  "abcd ", indices = \[0, 2\], sources = \[ "ab ", "ec "\], targets = \[ "eee ", "ffff "\]
**Output:**  "eeecd "
**Explanation:**
 "ab " occurs at index 0 in s, so we replace it with  "eee ".
 "ec " does not occur at index 2 in s, so we do nothing.

**Constraints:**

*   `1 <= s.length <= 1000`
*   `k == indices.length == sources.length == targets.length`
*   `1 <= k <= 100`
*   `0 <= indexes[i] < s.length`
*   `1 <= sources[i].length, targets[i].length <= 50`
*   `s` consists of only lowercase English letters.
*   `sources[i]` and `targets[i]` consist of only lowercase English letters.
Sum of Distances in Tree

There is an undirected connected tree with `n` nodes labeled from `0` to `n - 1` and `n - 1` edges.

You are given the integer `n` and the array `edges` where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the tree.

Return an array `answer` of length `n` where `answer[i]` is the sum of the distances between the `ith` node in the tree and all other nodes.

**Example 1:**

**Input:** n = 6, edges = \[\[0,1\],\[0,2\],\[2,3\],\[2,4\],\[2,5\]\]
**Output:** \[8,12,6,10,10,10\]
**Explanation:** The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer\[0\] = 8, and so on.

**Example 2:**

**Input:** n = 1, edges = \[\]
**Output:** \[0\]

**Example 3:**

**Input:** n = 2, edges = \[\[1,0\]\]
**Output:** \[1,1\]

**Constraints:**

*   `1 <= n <= 3 * 104`
*   `edges.length == n - 1`
*   `edges[i].length == 2`
*   `0 <= ai, bi < n`
*   `ai != bi`
*   The given input represents a valid tree.
Image Overlap

You are given two images, `img1` and `img2`, represented as binary, square matrices of size `n x n`. A binary matrix has only `0`s and `1`s as values.

We **translate** one image however we choose by sliding all the `1` bits left, right, up, and/or down any number of units. We then place it on top of the other image. We can then calculate the **overlap** by counting the number of positions that have a `1` in **both** images.

Note also that a translation does **not** include any kind of rotation. Any `1` bits that are translated outside of the matrix borders are erased.

Return _the largest possible overlap_.

**Example 1:**

**Input:** img1 = \[\[1,1,0\],\[0,1,0\],\[0,1,0\]\], img2 = \[\[0,0,0\],\[0,1,1\],\[0,0,1\]\]
**Output:** 3
**Explanation:** We translate img1 to right by 1 unit and down by 1 unit.
 
The number of positions that have a 1 in both images is 3 (shown in red).
 

**Example 2:**

**Input:** img1 = \[\[1\]\], img2 = \[\[1\]\]
**Output:** 1

**Example 3:**

**Input:** img1 = \[\[0\]\], img2 = \[\[0\]\]
**Output:** 0

**Constraints:**

*   `n == img1.length == img1[i].length`
*   `n == img2.length == img2[i].length`
*   `1 <= n <= 30`
*   `img1[i][j]` is either `0` or `1`.
*   `img2[i][j]` is either `0` or `1`.
Rectangle Overlap

An axis-aligned rectangle is represented as a list `[x1, y1, x2, y2]`, where `(x1, y1)` is the coordinate of its bottom-left corner, and `(x2, y2)` is the coordinate of its top-right corner. Its top and bottom edges are parallel to the X-axis, and its left and right edges are parallel to the Y-axis.

Two rectangles overlap if the area of their intersection is **positive**. To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two axis-aligned rectangles `rec1` and `rec2`, return `true` _if they overlap, otherwise return_ `false`.

**Example 1:**

**Input:** rec1 = \[0,0,2,2\], rec2 = \[1,1,3,3\]
**Output:** true

**Example 2:**

**Input:** rec1 = \[0,0,1,1\], rec2 = \[1,0,2,1\]
**Output:** false

**Example 3:**

**Input:** rec1 = \[0,0,1,1\], rec2 = \[2,2,3,3\]
**Output:** false

**Constraints:**

*   `rec1.length == 4`
*   `rec2.length == 4`
*   `-109 <= rec1[i], rec2[i] <= 109`
*   `rec1` and `rec2` represent a valid rectangle with a non-zero area.
New 21 Game

Alice plays the following game, loosely based on the card game **"21 "**.

Alice starts with `0` points and draws numbers while she has less than `k` points. During each draw, she gains an integer number of points randomly from the range `[1, maxPts]`, where `maxPts` is an integer. Each draw is independent and the outcomes have equal probabilities.

Alice stops drawing numbers when she gets `k` **or more points**.

Return the probability that Alice has `n` or fewer points.

Answers within `10-5` of the actual answer are considered accepted.

**Example 1:**

**Input:** n = 10, k = 1, maxPts = 10
**Output:** 1.00000
**Explanation:** Alice gets a single card, then stops.

**Example 2:**

**Input:** n = 6, k = 1, maxPts = 10
**Output:** 0.60000
**Explanation:** Alice gets a single card, then stops.
In 6 out of 10 possibilities, she is at or below 6 points.

**Example 3:**

**Input:** n = 21, k = 17, maxPts = 10
**Output:** 0.73278

**Constraints:**

*   `0 <= k <= n <= 104`
*   `1 <= maxPts <= 104`
Push Dominoes

There are `n` dominoes in a line, and we place each domino vertically upright. In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left. Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

You are given a string `dominoes` representing the initial state where:

*   `dominoes[i] = 'L'`, if the `ith` domino has been pushed to the left,
*   `dominoes[i] = 'R'`, if the `ith` domino has been pushed to the right, and
*   `dominoes[i] = '.'`, if the `ith` domino has not been pushed.

Return _a string representing the final state_.

**Example 1:**

**Input:** dominoes =  "RR.L "
**Output:**  "RR.L "
**Explanation:** The first domino expends no additional force on the second domino.

**Example 2:**

**Input:** dominoes =  ".L.R...LR..L.. "
**Output:**  "LL.RR.LLRRLL.. "

**Constraints:**

*   `n == dominoes.length`
*   `1 <= n <= 105`
*   `dominoes[i]` is either `'L'`, `'R'`, or `'.'`.
Similar String Groups

Two strings `X` and `Y` are similar if we can swap two letters (in different positions) of `X`, so that it equals `Y`. Also two strings `X` and `Y` are similar if they are equal.

For example, `"tars "` and `"rats "` are similar (swapping at positions `0` and `2`), and `"rats "` and `"arts "` are similar, but `"star "` is not similar to `"tars "`, `"rats "`, or `"arts "`.

Together, these form two connected groups by similarity: `{ "tars ", "rats ", "arts "}` and `{ "star "}`. Notice that `"tars "` and `"arts "` are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list `strs` of strings where every string in `strs` is an anagram of every other string in `strs`. How many groups are there?

**Example 1:**

**Input:** strs = \[ "tars ", "rats ", "arts ", "star "\]
**Output:** 2

**Example 2:**

**Input:** strs = \[ "omv ", "ovm "\]
**Output:** 1

**Constraints:**

*   `1 <= strs.length <= 300`
*   `1 <= strs[i].length <= 300`
*   `strs[i]` consists of lowercase letters only.
*   All words in `strs` have the same length and are anagrams of each other.
Magic Squares In Grid

A `3 x 3` magic square is a `3 x 3` grid filled with distinct numbers **from** `1` **to** `9` such that each row, column, and both diagonals all have the same sum.

Given a `row x col` `grid` of integers, how many `3 x 3` "magic square " subgrids are there? (Each subgrid is contiguous).

**Example 1:**

**Input:** grid = \[\[4,3,8,4\],\[9,5,1,9\],\[2,7,6,2\]\]
**Output:** 1
**Explanation:** 
The following subgrid is a 3 x 3 magic square:
 
while this one is not:
 
In total, there is only one magic square inside the given grid.

**Example 2:**

**Input:** grid = \[\[8\]\]
**Output:** 0

**Constraints:**

*   `row == grid.length`
*   `col == grid[i].length`
*   `1 <= row, col <= 10`
*   `0 <= grid[i][j] <= 15`
Keys and Rooms

There are `n` rooms labeled from `0` to `n - 1` and all the rooms are locked except for room `0`. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of **distinct keys** in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array `rooms` where `rooms[i]` is the set of keys that you can obtain if you visited room `i`, return `true` _if you can visit **all** the rooms, or_ `false` _otherwise_.

**Example 1:**

**Input:** rooms = \[\[1\],\[2\],\[3\],\[\]\]
**Output:** true
**Explanation:** 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

**Example 2:**

**Input:** rooms = \[\[1,3\],\[3,0,1\],\[2\],\[0\]\]
**Output:** false
**Explanation:** We can not enter room number 2 since the only key that unlocks it is in that room.

**Constraints:**

*   `n == rooms.length`
*   `2 <= n <= 1000`
*   `0 <= rooms[i].length <= 1000`
*   `1 <= sum(rooms[i].length) <= 3000`
*   `0 <= rooms[i][j] < n`
*   All the values of `rooms[i]` are **unique**.
Split Array into Fibonacci Sequence

You are given a string of digits `num`, such as `"123456579 "`. We can split it into a Fibonacci-like sequence `[123, 456, 579]`.

Formally, a **Fibonacci-like** sequence is a list `f` of non-negative integers such that:

*   `0 <= f[i] < 231`, (that is, each integer fits in a **32-bit** signed integer type),
*   `f.length >= 3`, and
*   `f[i] + f[i + 1] == f[i + 2]` for all `0 <= i < f.length - 2`.

Note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number `0` itself.

Return any Fibonacci-like sequence split from `num`, or return `[]` if it cannot be done.

**Example 1:**

**Input:** num =  "1101111 "
**Output:** \[11,0,11,11\]
**Explanation:** The output \[110, 1, 111\] would also be accepted.

**Example 2:**

**Input:** num =  "112358130 "
**Output:** \[\]
**Explanation:** The task is impossible.

**Example 3:**

**Input:** num =  "0123 "
**Output:** \[\]
**Explanation:** Leading zeroes are not allowed, so  "01 ",  "2 ",  "3 " is not valid.

**Constraints:**

*   `1 <= num.length <= 200`
*   `num` contains only digits.
Guess the Word

You are given an array of unique strings `words` where `words[i]` is six letters long. One word of `words` was chosen as a secret word.

You are also given the helper object `Master`. You may call `Master.guess(word)` where `word` is a six-letter-long string, and it must be from `words`. `Master.guess(word)` returns:

*   `-1` if `word` is not from `words`, or
*   an integer representing the number of exact matches (value and position) of your guess to the secret word.

There is a parameter `allowedGuesses` for each test case where `allowedGuesses` is the maximum number of times you can call `Master.guess(word)`.

For each test case, you should call `Master.guess` with the secret word without exceeding the maximum number of allowed guesses. You will get:

*   **`"Either you took too many guesses, or you did not find the secret word. "`** if you called `Master.guess` more than `allowedGuesses` times or if you did not call `Master.guess` with the secret word, or
*   **`"You guessed the secret word correctly. "`** if you called `Master.guess` with the secret word with the number of calls to `Master.guess` less than or equal to `allowedGuesses`.

The test cases are generated such that you can guess the secret word with a reasonable strategy (other than using the bruteforce method).

**Example 1:**

**Input:** secret =  "acckzz ", words = \[ "acckzz ", "ccbazz ", "eiowzz ", "abcczz "\], allowedGuesses = 10
**Output:** You guessed the secret word correctly.
**Explanation:**
master.guess( "aaaaaa ") returns -1, because  "aaaaaa " is not in wordlist.
master.guess( "acckzz ") returns 6, because  "acckzz " is secret and has all 6 matches.
master.guess( "ccbazz ") returns 3, because  "ccbazz " has 3 matches.
master.guess( "eiowzz ") returns 2, because  "eiowzz " has 2 matches.
master.guess( "abcczz ") returns 4, because  "abcczz " has 4 matches.
We made 5 calls to master.guess, and one of them was the secret, so we pass the test case.

**Example 2:**

**Input:** secret =  "hamada ", words = \[ "hamada ", "khaled "\], allowedGuesses = 10
**Output:** You guessed the secret word correctly.
**Explanation:** Since there are two words, you can guess both.

**Constraints:**

*   `1 <= words.length <= 100`
*   `words[i].length == 6`
*   `words[i]` consist of lowercase English letters.
*   All the strings of `wordlist` are **unique**.
*   `secret` exists in `words`.
*   `10 <= allowedGuesses <= 30`
Backspace String Compare

Given two strings `s` and `t`, return `true` _if they are equal when both are typed into empty text editors_. `'#'` means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

**Example 1:**

**Input:** s =  "ab#c ", t =  "ad#c "
**Output:** true
**Explanation:** Both s and t become  "ac ".

**Example 2:**

**Input:** s =  "ab## ", t =  "c#d# "
**Output:** true
**Explanation:** Both s and t become  " ".

**Example 3:**

**Input:** s =  "a#c ", t =  "b "
**Output:** false
**Explanation:** s becomes  "c " while t becomes  "b ".

**Constraints:**

*   `1 <= s.length, t.length <= 200`
*   `s` and `t` only contain lowercase letters and `'#'` characters.

**Follow up:** Can you solve it in `O(n)` time and `O(1)` space?