Aaron Teo

← Back to home

[LeetCode 1472] [Medium] Design Browser History

Question

You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.

Implement the BrowserHistory class:

  • 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.

Example:

Input:

["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]

[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]

Output:

[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Explanation:

BrowserHistory browserHistory = new BrowserHistory("leetcode.com");

browserHistory.visit("google.com"); // You are in "leetcode.com". Visit "google.com"

browserHistory.visit("facebook.com"); // You are in "google.com". Visit "facebook.com"

browserHistory.visit("youtube.com"); // You are in "facebook.com". Visit "youtube.com"

browserHistory.back(1); // You are in "youtube.com", move back to "facebook.com" return "facebook.com"

browserHistory.back(1); // You are in "facebook.com", move back to "google.com" return "google.com"

browserHistory.forward(1); // You are in "google.com", move forward to "facebook.com" return "facebook.com"

browserHistory.visit("linkedin.com"); // You are in "facebook.com". Visit "linkedin.com"

browserHistory.forward(2); // You are in "linkedin.com", you cannot move forward any steps.

browserHistory.back(2); // You are in "linkedin.com", move back two steps to "facebook.com" then to "google.com". return "google.com"

browserHistory.back(7); // You are in "google.com", you can move back only one step to "leetcode.com". return "leetcode.com"

Solution

Using a doubly linked list to navigate, will allow us to develop the required mechanisms for this problem. First we declare a doubly linked list node definition. After that we will use the strategies below for the following functions that are required for implementation:

  • def __init__(self, homepage): On initialisation, we will initialise the self.tail property which will contain the current pointer position for our navigation.
  • def visit(self, url): When a page is visited, we will create a new doubly linked list node to hold the value of the newly visited url, and then connect this new linked list node to the last previously visited node by reassigning the prev and next properties of these nodes. Lastly, we will update the self.tail to the newly visited node.
  • def back(self, steps): For each step of navigation backwards, we will first check if it's possible to navigate back, if there are no more nodes to the left (in front) of our current node, then we now know that it's the maximum position we can move backwards. Else, simply move till there are no more steps left. Then, return that current node.
  • def forward(self, steps): Similarly, for each step of navigation forward, we will check if there are any more nodes to the right of our current node, if not, return the maximum possible navigation forward. Else, we can continue the navigation forward till the remaining steps hits 0. Then return the current node.

Code

class ListNode():
    def __init__(self, val = 0):
        self.val = val
        self.prev = None
        self.next = None

class BrowserHistory(object):

    def __init__(self, homepage):
        """
        :type homepage: str
        """
        startingNode = ListNode(homepage)
        self.tail = startingNode

    def visit(self, url):
        """
        :type url: str
        :rtype: None
        """
        newNodeToVisit = ListNode(url)
        self.tail.next = newNodeToVisit
        newNodeToVisit.prev = self.tail
        self.tail = self.tail.next

    def back(self, steps):
        """
        :type steps: int
        :rtype: str
        """
        while steps > 0 and self.tail.prev:
            steps -= 1            
            self.tail = self.tail.prev
        return self.tail.val

    def forward(self, steps):
        """
        :type steps: int
        :rtype: str
        """
        while steps > 0 and self.tail.next:
            steps -= 1
            self.tail = self.tail.next
        return self.tail.val


# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)
← Back to home