Stack Basics

Table of Contents

• 1441. Build an Array With Stack Operations (Medium)
• 844. Backspace String Compare (Easy)
• 682. Baseball Game (Easy)
• 2390. Removing Stars From a String (Medium)
• 1472. Design Browser History (Medium)
• 946. Validate Stack Sequences (Medium)
• 3412. Find Mirror Score of a String (Medium)
• 71. Simplify Path (Medium)

1441. Build an Array With Stack Operations

• LeetCode | LeetCode CH (Medium)

• Tags: array, stack, simulation

1441. Build an Array With Stack Operations - Python Solution

from typing import List


# Stack
def buildArray(target: List[int], n: int) -> List[str]:
    res = []
    m, i, j = len(target), 1, 0

    while i <= n and j < m:
        res.append("Push")
        if target[j] != i:
            res.append("Pop")
        else:
            j += 1
        i += 1

    return res


target = [1, 3, 4]
n = 4
print(buildArray(target, n))
# ['Push', 'Push', 'Pop', 'Push', 'Push']

844. Backspace String Compare

• LeetCode | LeetCode CH (Easy)

• Tags: two pointers, string, stack, simulation

844. Backspace String Compare - Python Solution

def backspaceCompare(s: str, t: str) -> bool:

    def build(text):
        stack = []

        for char in text:
            if char != "#":
                stack.append(char)
            elif stack:
                stack.pop()

        return "".join(stack)

    return build(s) == build(t)


print(backspaceCompare("ab#c", "ad#c"))  # True

682. Baseball Game

• LeetCode | LeetCode CH (Easy)

• Tags: array, stack, simulation

682. Baseball Game - Python Solution

from typing import List


# Stack
def calPoints(operations: List[str]) -> int:
    stack = []

    for op in operations:
        if op == "+":
            stack.append(stack[-2] + stack[-1])
        elif op == "D":
            stack.append(2 * stack[-1])
        elif op == "C":
            stack.pop()
        else:
            stack.append(int(op))

    return sum(stack)


ops = ["5", "2", "C", "D", "+"]
print(calPoints(ops))  # 30

2390. Removing Stars From a String

• LeetCode | LeetCode CH (Medium)

• Tags: string, stack, simulation

• Remove all * characters and their adjacent characters from the string.

• Steps for the string leet**cod*e:

char	action	stack
l	push	"l"
e	push	"le"
e	push	"lee"
t	push	"leet"
*	pop	"lee"
*	pop	"le"
c	push	"lec"
o	push	"leco"
d	push	"lecod"
*	pop	"leco"
e	push	"lecoe"

2390. Removing Stars From a String - Python Solution

# Stack
def removeStars(s: str) -> str:
    stack = []

    for char in s:
        if char == "*":
            stack.pop()
        else:
            stack.append(char)

    return "".join(stack)


s = "leet**cod*e"
print(removeStars(s))  # "lecoe"

1472. Design Browser History

• LeetCode | LeetCode CH (Medium)

• Tags: array, linked list, stack, design, doubly linked list, data stream

946. Validate Stack Sequences

• LeetCode | LeetCode CH (Medium)

• Tags: array, stack, simulation

3412. Find Mirror Score of a String

• LeetCode | LeetCode CH (Medium)

• Tags: hash table, string, stack, simulation

71. Simplify Path

• LeetCode | LeetCode CH (Medium)

• Tags: string, stack

Comments