Given two strings s and t, return trueif 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?
Solution
Approach #0
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
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)
}
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].
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
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
}
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:
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
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
}
