Method 1
class BrowserHistory:
#Two Stacks to save the history for back and forward usage
#TC: O(1) for init and visit, O(steps) for back and forward
#SC: O(n) fpr n input homepage
def __init__(self, homepage: str):
self.L = [homepage]
self.idx = 0
self.upperbound = 0
def visit(self, url: str) -> None:
if self.idx == len(self.L) - 1:
self.L.append(url)
self.idx += 1
else:
self.idx += 1
self.L[self.idx] = url
self.upperbound = self.idx
def back(self, steps: int) -> str:
self.idx = max(0, self.idx-steps)
return self.L[self.idx]
def forward(self, steps: int) -> str:
self.idx = min(self.idx+steps, self.upperbound)
return self.L[self.idx]
Method 2:
class BrowserHistory:
#Use one stack to store browsing history.
#Use a global idx to denote the current location
#Define a variable upperbound
#History beyond the upperbound should be not considered
#TC: O(1) for all operations
#SC: O(n) fpr n input homepage
def __init__(self, homepage: str):
self.L = [homepage]
self.idx = 0
self.upperbound = 0
def visit(self, url: str) -> None:
if self.idx == len(self.L) - 1:
self.L.append(url)
self.idx += 1
else:
self.idx += 1
self.L[self.idx] = url
self.upperbound = self.idx
def back(self, steps: int) -> str:
self.idx = max(0, self.idx-steps)
return self.L[self.idx]
def forward(self, steps: int) -> str:
self.idx = min(self.idx+steps, self.upperbound)
return self.L[self.idx]