Design Browser History - Leetcode Solution

Design Browser History problem on LeetCode is a problem that requires you to implement a class BrowserHistory that represents the history of a browser as a doubly linked list. The browser history should support the following operations:

1. visit(url): Adds a new url to the history and sets it as the current page.
2. back(steps): Moves back by steps in the history. If there are not enough pages in the history, then move to the first page.
3. forward(steps): Moves forward by steps in the history. If there are not enough pages in the history, then move to the last page.
4. getCurrentUrl(): Returns the current url.
5. clearHistory(): Clears the history.

To solve this problem, we can implement the BrowserHistory class using a doubly linked list. We will have a head and a tail pointer that will represent the first and last nodes in the list respectively. We will also keep track of the current node, which will be the node that represents the current page.

To implement the visit(url) operation, we will create a new node and append it to the end of the list. We will set the current node to this new node.

To implement the back(steps) operation, we will move back steps nodes in the list, starting from the current node. If we reach the head of the list, we will stop at the head. We will update the current node to be the node we stopped at.

To implement the forward(steps) operation, we will move forward steps nodes in the list, starting from the current node. If we reach the tail of the list, we will stop at the tail. We will update the current node to be the node we stopped at.

To implement the getCurrentUrl() operation, we will return the url of the current node.

To implement the clearHistory() operation, we will set the head and tail pointers to null, and set the current node to null.

Here's the code implementation in Java:

class Node { String url; Node prev; Node next; public Node(String url) { this.url = url; this.prev = null; this.next = null; } }

class BrowserHistory { Node head; Node tail; Node curr; public BrowserHistory(String homepage) { head = new Node(homepage); tail = head; curr = head; } public void visit(String url) { Node node = new Node(url); tail.next = node; node.prev = tail; tail = node; curr = tail; } public String back(int steps) { while (curr.prev != null && steps > 0) { curr = curr.prev; steps--; } return curr.url; } public String forward(int steps) { while (curr.next != null && steps > 0) { curr = curr.next; steps--; } return curr.url; } public String getCurrentUrl() { return curr.url; } public void clearHistory() { head = null; tail = null; curr = null; } }

The time complexity of all the operations is O(steps) because we are traversing steps nodes in the list. The space complexity of the class is O(n) because we are creating and storing n nodes in the doubly linked list.

1