Sponsored
Sponsored
This approach involves using a list (or similar data structure) to keep track of the pages visited. We use an index to keep track of the current page. Visiting a new page from the current page will truncate the list beyond the current index before adding the new page. Moving back or forward adjusts the index within the bounds of the list.
Time Complexity: Each operation (visit, back, forward) is O(1) on average due to direct index manipulation or list slicing.
Space Complexity: O(n), where n is the number of URLs stored in history.
1class BrowserHistory:
2 def __init__(self, homepage: str):
3 self.history = [homepage] # List to maintain the browsing history
4 self.current = 0 # Current index in history
5
6 def visit(self, url: str) -> None:
7 # Discard forward history and append new entry
8 self.history = self.history[:self.current+1]
9 self.history.append(url)
10 self.current += 1
11
12 def back(self, steps: int) -> str:
13 # Move back, ensuring we do not go past the first page
14 self.current = max(0, self.current - steps)
15 return self.history[self.current]
16
17 def forward(self, steps: int) -> str:
18 # Move forward, ensuring we do not go beyond the last visited page
19 self.current = min(len(self.history) - 1, self.current + steps)
20 return self.history[self.current]In this implementation, the 'history' list keeps all the visited pages. 'current' is an integer that marks our current position in the history. When we visit a new URL, the function slices the list up to 'current' and appends the new URL, making sure to remove any forward history. The 'back' and 'forward' functions only adjust the current position and ensure it is within valid bounds.
This approach uses two stacks: one to store backward paths and another to store forward paths. The current page is not stored in the stack, but rather observed as the topmost element of the backward stack. The back function pops elements from the backward stack to the forward stack as necessary, and the forward function performs the opposite action. This effectively mimicks the process of moving through the history as we go back and forth.
Time Complexity: Each call to visit, back, or forward is O(steps) due to operations over respective stacks.
Space Complexity: O(n) for maintaining stacks with n pages.
1using System.Collections.Generic;
public class BrowserHistory {
private Stack<string> backStack = new Stack<string>();
private Stack<string> forwardStack = new Stack<string>();
private string current;
public BrowserHistory(string homepage) {
current = homepage;
}
public void Visit(string url) {
backStack.Push(current);
current = url;
forwardStack.Clear();
}
public string Back(int steps) {
while (steps > 0 && backStack.Count > 0) {
forwardStack.Push(current);
current = backStack.Pop();
steps--;
}
return current;
}
public string Forward(int steps) {
while (steps > 0 && forwardStack.Count > 0) {
backStack.Push(current);
current = forwardStack.Pop();
steps--;
}
return current;
}
}This C# solution uses the built-in Stack class for efficient forward and backward browsing management, benefiting from automatic memory and stack management.