1472. Design Browser History - cocoder39/coco39_LC GitHub Wiki

1472. Design Browser History

First thought: single stack which doesn't optimize visit() call

class BrowserHistory:

    def __init__(self, homepage: str):
        self.history = [homepage]
        self.cursor = 0
        

    def visit(self, url: str) -> None:
        k = len(self.history) - (self.cursor + 1)
        for i in range(k):
            self.history.pop()
        self.history.append(url)
        self.cursor += 1
        

    def back(self, steps: int) -> str:
        while steps > 0 and self.cursor - 1 >= 0:
            self.cursor -= 1
            steps -= 1
        return self.history[self.cursor]
        

    def forward(self, steps: int) -> str:
        while steps > 0 and self.cursor + 1 < len(self.history):
            self.cursor += 1
            steps -= 1
        return self.history[self.cursor]

Optimization: double stacks

class BrowserHistory:

    def __init__(self, homepage: str):
        self.backStack = [homepage]
        self.forwardStack = []
        

    def visit(self, url: str) -> None:
        self.backStack.append(url)
        self.forwardStack = []
        
    def back(self, steps: int) -> str:
        while steps > 0 and len(self.backStack) > 1:
            url = self.backStack.pop()
            self.forwardStack.append(url)
            steps -= 1
        return self.backStack[-1]

    def forward(self, steps: int) -> str:
        while steps > 0 and self.forwardStack:
            url = self.forwardStack.pop()
            self.backStack.append(url)
            steps -= 1
        return self.backStack[-1]