1472.Design Browser History

Question Link:https://leetcode.com/problems/design-browser-history/

Explanation:

The question is asking to perform four operation basically :

• BrowserHistory(string homepage) Initializes the object with the homepage of the browser.

• void visit(string url) Visits url from the current page. It clears up all the forward history.

• string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.

• string forward(int steps) Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps.

As we can move both forward and backward direction and need flexibility to move current place to given url .

The datastucture comes to mind is :Doubly Linkedlist bcaz we have to go forward as well as backward direction and all should be connected. First we need to create template for doubly linked list :

class Node{
public:
    string url;
    Node* prev;
    Node* next;

    Node(string url){
        this->url = url;
        prev = NULL;
        next = NULL;
    }
};

Now we are ready to implement four function

First one is Browser History , Here just we need to initialize object with given url .

class BrowserHistory {
private:
    Node *root;
public:
    BrowserHistory(string homepage) {
        root = new Node(homepage);
    }

Now second one visit, we have to add new tab with given url and connect both (for that we are using simply doubly linked list).

 void visit(string url) {
        Node* node = new Node(url);
        root->next = node;
        node->prev = root;
        root = root->next;
    }

Third : Back :just we have to traverse back to get desired url.

 string back(int steps) {
        for(int i = 0; i<steps && root->prev != NULL; i++){
            root = root->prev;
        }
        return root->url;
    }

Fourth Forward: just we have to traverse next to get desired url.

 string forward(int steps) {
        for(int i = 0; i<steps && root->next != NULL; i++){
            root = root->next;
        }
        return root->url;
    }