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.
1#include <vector>
2#include <string>
3
4class BrowserHistory {
5 std::vector<std::string> history;
6 int current;
7public:
8 BrowserHistory(std::string homepage) {
9 history.push_back(homepage);
10 current = 0;
11 }
12
13 void visit(std::string url) {
14 history.resize(current + 1);
15 history.push_back(url);
16 current++;
17 }
18
19 std::string back(int steps) {
20 current = std::max(0, current - steps);
21 return history[current];
22 }
23
24 std::string forward(int steps) {
25 current = std::min((int)history.size() - 1, current + steps);
26 return history[current];
27 }
28};The C++ implementation uses a vector to store the browsing history. Similar to other solutions, we maintain a 'current' index. On visiting a new URL, we truncate the vector and add the new page. The 'back' and 'forward' methods adjust the position logically.
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.