054.md

1472. Design Browser History

Difficulty: 🟡 Medium

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"

Constraints:

• 1 <= homepage.length <= 20
• 1 <= url.length <= 20
• 1 <= steps <= 100
• homepage and url consist of '.' or lower case English letters.
• At most 5000 calls will be made to visit, back, and forward

Solutions

Example solution

class VisitedPage:
    def __init__(self, url: str):
        self.next = None
        self.prev = None
        self.url = url

class BrowserHistory:
    def __init__(self, homepage: str):
        self._current = VisitedPage(homepage)

    def visit(self, url: str) -> None:
        temp = VisitedPage(url)
        temp.prev = self._current
        self._current.next = temp
        self._current = temp

    def back(self, steps: int) -> str:
        while steps and self._current.prev:
            self._current = self._current.prev
            steps -= 1
        return self._current.url

    def forward(self, steps: int) -> str:
        while steps and self._current.next:
            self._current =self._current.next
            steps -= 1
        return self._current.url

# 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)

The given solution implements the BrowserHistory class using a linked list data structure. Each node in the linked list represents a visited page, and it contains the URL as well as references to the next and previous nodes.

Here is a step-by-step overview of the solution:

1. Define a helper class VisitedPage that represents a visited page in the browser's history. It has attributes next, prev, and url to store the references to the next and previous pages, as well as the URL of the current page.
2. In the BrowserHistory class, initialize the _current attribute with the VisitedPage object representing the homepage.
3. Implement the visit method:
   • Create a new VisitedPage object with the given URL.
   • Set the prev reference of the new page to the current page.
   • Set the next reference of the current page to the new page.
   • Update the _current attribute to the new page.
4. Implement the back method:
   • Iterate steps times:
     • If the current page has a previous page, update the _current attribute to the previous page.
   • Return the URL of the current page.
5. Implement the forward method:
   • Iterate steps times:
     • If the current page has a next page, update the _current attribute to the next page.
   • Return the URL of the current page.

Complexity Analysis

The time complexity for the visit, back, and forward methods is O(steps) since we iterate steps times to move back or forward in the history.

The space complexity is O(1) since we use a constant amount of additional space.

Summary

The given solution implements the BrowserHistory class using a linked list. It allows us to visit URLs, go back or forward in the history, and returns the current URL. The time complexity of the methods is O(steps), and the space complexity is O(1).

NB: If you want to get community points please suggest solutions in other languages as merge requests.