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.
1using System;
2using System.Collections.Generic;
3
4public class BrowserHistory {
5 private List<string> history;
6 private int current;
7
8 public BrowserHistory(string homepage) {
9 history = new List<string>() { homepage };
10 current = 0;
11 }
12
13 public void Visit(string url) {
14 history = history.GetRange(0, current + 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[current];
22 }
23
24 public string Forward(int steps) {
25 current = Math.Min(history.Count - 1, current + steps);
26 return history[current];
27 }
28}In the C# implementation, we use a List<string> to track URLs and an integer 'current'. The 'Visit' method updates the list by making a new range ending at 'current', then appends the new site. The 'Back' and 'Forward' methods calculate the appropriate page index.
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 JavaScript, two arrays serve as stacks. When visiting a new site, the forward history is cleared. The back and forward methods modify these stacks to simulate historical navigation.