# 2022-05-31

## [844. Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/)

### Description

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.&#x20;

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

### Solution

#### Approach #0

```go
func backspaceCompare(s string, t string) bool {
    m, n := len(s), len(t)
    i, j := m-1, n-1
    for i >= 0 || j >= 0 {
        i, j = goBack(s, i), goBack(t, j)
        if i >= 0 && j >= 0 && s[i] != t[j] {
            return false
        }
        i--
        j--
    }
    return i == j
}

func goBack(s string, i int) int {
    count := 0
    j := i
    for j >= 0 && (s[j] == '#' || count > 0) {
        if s[j] != '#' {
            count--
        } else {
            count++
        }
        j--
    }
    return j
}
```

#### Approach #1

```go
func backspaceCompare(s string, t string) bool {
    return build(s) == build(t)
}

func build(s string) string {
    var st []rune
    for _, ch := range s {
        if ch == '#' {
            n := len(st)
            if n > 0 {
                st = st[:n-1]
            }
        } else {
            st = append(st, ch)
        }
    }
    return string(st)
}
```

## [986. Interval List Intersections](https://leetcode.com/problems/interval-list-intersections/)

### Description

You are given two lists of closed intervals, `firstList` and `secondList`, where `firstList[i] = [start[i], end[i]]` and `secondList[j] = [start[j], end[j]]`. Each list of intervals is pairwise **disjoint** and in **sorted order**.

Return *the intersection of these two interval lists*.

A **closed interval** `[a, b]` (with `a <= b`) denotes the set of real numbers `x` with `a <= x <= b`.

The **intersection** of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of `[1, 3]` and `[2, 4]` is `[2, 3]`.

**Example 1:**

![](https://img.content.cc/a/2022/05/31/08-42-02-011-cc562333c497dcf782c38a52753cc7cd-286873.png)

```
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
```

**Example 2:**

```
Input: firstList = [[1,3],[5,9]], secondList = []
Output: []
```

**Constraints:**

* `0 <= firstList.length, secondList.length <= 1000`
* `firstList.length + secondList.length >= 1`
* `0 <= start[i] < end[i] <= 10^9`
* `end[i] < start[i+1]`
* `0 <= start[j] < end[j] <= 10^9`
* `end[j] < start[j+1]`

### Solution

#### Approach #0

```go
func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
    i, j := 0, 0
    m, n := len(firstList), len(secondList)
    var ans [][]int
    for i < m && j < n {
        a1, b1 := firstList[i][0], firstList[i][1]
        a2, b2 := secondList[j][0], secondList[j][1]
        if a1 <= b2 && b1 >= a2 {
            x, y := a1, b2
            if a1 <= a2 {
                x = a2
            }
            if b1 <= b2 {
                y = b1
            }
            ans = append(ans, []int{x, y})
        }
        if b1 < b2 {
            i++
        } else {
            j++
        }
    }
    return ans
}
```

#### Approach #1

```go
func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
    i, j := 0, 0
    var ans [][]int
    for i < len(firstList) && j < len(secondList) {
        low := max(firstList[i][0], secondList[j][0])
        high := min(firstList[i][1], secondList[j][1])
        if low <= high {
            ans = append(ans, []int{low, high})
        }
        if firstList[i][1] < secondList[j][1] {
            i++
        } else {
            j++
        }
    }
    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```

## [11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/)

### Description

You are given an integer array `height` of length `n`. There are `n` vertical lines drawn such that the two endpoints of the `ith` line are `(i, 0)` and `(i, height[i])`.

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return *the maximum amount of water a container can store*.

**Notice** that you may not slant the container.

**Example 1:**

![](https://img.content.cc/a/2022/05/31/08-43-53-733-9daebb6ebbdb925763fbd31e9a7aa329-db83c2.jpeg)

```
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
```

**Example 2:**

```
Input: height = [1,1]
Output: 1
```

**Constraints:**

* `n == height.length`
* `2 <= n <= 10^5`
* `0 <= height[i] <= 10^4`

### Solution

#### Approach #0

```go
func maxArea(height []int) int {
    n := len(height)
    i, j := 0, n-1
    var ans int
    for i < j {
        ans = max(ans, (j-i)*min(height[i], height[j]))
        if height[i] < height[j] {
            i++
        } else {
            j--
        }
    }
    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```