Skip to content

Stack Basics

Table of Contents

1441. Build an Array With Stack Operations

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

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

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

"""
-   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" |
"""


# 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

class BrowserHistory:

    def __init__(self, homepage: str):
        self.hist = [homepage]
        self.cur = 0

    def visit(self, url: str) -> None:
        self.cur += 1
        del self.hist[self.cur :]
        self.hist.append(url)

    def back(self, steps: int) -> str:
        self.cur = max(self.cur - steps, 0)
        return self.hist[self.cur]

    def forward(self, steps: int) -> str:
        self.cur = min(self.cur + steps, len(self.hist) - 1)
        return self.hist[self.cur]


if __name__ == "__main__":
    obj = BrowserHistory("leetcode.com")
    obj.visit("google.com")
    obj.visit("facebook.com")
    obj.visit("youtube.com")
    assert obj.back(1) == "facebook.com"
    assert obj.back(1) == "google.com"
    assert obj.forward(1) == "facebook.com"
    obj.visit("linkedin.com")
    assert obj.forward(2) == "linkedin.com"
    assert obj.back(2) == "google.com"
    assert obj.back(7) == "leetcode.com"

946. Validate Stack Sequences

3412. Find Mirror Score of a String

71. Simplify Path

def simplify_path_stack(path: str) -> str:
    if not path:
        return "/"

    stack = []

    for p in path.split("/"):
        if p == "" or p == ".":
            continue
        if p != "..":
            stack.append(p)
        elif stack:
            stack.pop()
    return "/" + "/".join(stack)


def test_simplify_path_stack():
    assert simplify_path_stack("/home/") == "/home"
    assert simplify_path_stack("/../") == "/"
    assert simplify_path_stack("/home//foo/") == "/home/foo"
    assert simplify_path_stack("/a/./b/../../c/") == "/c"

Comments