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.
1import java.util.ArrayList;
2
3class BrowserHistory {
4 private ArrayList<String> history;
5 private int current;
6
7 public BrowserHistory(String homepage) {
8 history = new ArrayList<>();
9 history.add(homepage);
10 current = 0;
11 }
12
13 public void visit(String url) {
14 while(history.size() > current + 1) history.remove(history.size() - 1);
15 history.add(url);
16 current++;
17 }
18
19 public String back(int steps) {
20 current = Math.max(0, current - steps);
21 return history.get(current);
22 }
23
24 public String forward(int steps) {
25 current = Math.min(history.size() - 1, current + steps);
26 return history.get(current);
27 }
28}In Java, we use an ArrayList to store the history and a 'current' index to denote the current page in the history. The 'visit' method updates the list by trimming any forward history. The 'back' and 'forward' methods adjust the current index based on the given steps but ensure it stays within the 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.
In this Python solution, we use back_stack and forward_stack to keep track of visited pages. 'visit': Pushes the current page to back_stack and resets forward_stack. 'back': Pops pages from back_stack to forward_stack up to steps. 'forward': Pops pages from forward_stack back to back_stack up to steps.