Design Browser History
Problem Description
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 thehomepageof the browser.void visit(string url)Visitsurlfrom the current page. It clears up all the forward history.string back(int steps)Movestepsback in history. If you can only returnxsteps in the history andsteps > x, you will return onlyxsteps. Return the currenturlafter moving back in history at moststeps.string forward(int steps)Movestepsforward in history. If you can only forwardxsteps in the history andsteps > x, you will forward onlyxsteps. Return the currenturlafter forwarding in history at moststeps.
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:
Constraints:
1 <= homepage.length <= 201 <= url.length <= 201 <= steps <= 100homepageandurlconsist of '.' or lower case English letters.- At most
5000calls will be made tovisit,back, andforward.
Solve it on LeetCode
Approaches
1. Using a List to Store History
Intuition:
The most straightforward approach to manage browsing history is by using a list. Each time we visit a new URL, we can append it to the list from the current position, effectively simulating moving forward or backward in browser history.
Execution:
- Use an ArrayList to store the web pages.
- Maintain an integer
currentto track the index of the current web page. - On visiting a new page, all forward history (if any) is removed, and the new URL is appended.
Details:
- visit(String url): Add the url to the history at the current position and remove any forward history. Update the current position.
- back(int steps): Move the current position back by
stepsor until reaching the first page. - forward(int steps): Move the current position forward by
stepsor until reaching the last page.
Code:
- Time Complexity:
visit(): O(N) in the worst case (removing forward history), where N is the size of the current list.back()andforward(): O(1).- Space Complexity: O(N), where N is the number of URLs stored.
2. Using Two Stacks
Intuition:
To optimize the operations for forward and backward navigation, two stacks can be used:
- One stack to hold the history we can go back to.
- Another stack to hold the history we can move forward to.
Execution:
- Use a current variable to track the active page.
- On
visit, clear the forward stack and push the current page to the backward stack before visiting the new page. - For
back, push the current page to the forward stack and pop from the backward stack. - For
forward, pop from the forward stack and push to the backward stack.
Details:
- visit(String url): Push current page to the back stack, clear forward stack, and set visited page as current.
- back(int steps): Move as many steps back from the back stack, adjusting the current page.
- forward(int steps): Move as many steps forward from the forward stack, adjusting the current page.
Code:
- Time Complexity:
visit(): O(1). Adding to stack and clearing another.back()andforward(): O(steps). Maximum O(N) where N is the number of URLs.- Space Complexity: O(N), where N is the number of URLs stored.