Problem Description

This problem asks you to implement a web crawler that explores web pages starting from a given URL and collects all URLs that belong to the same hostname.

The web crawler should follow these rules:

1. Start from a given URL (startUrl) and explore linked pages from there.

2. Use the HtmlParser interface to get URLs from any webpage by calling HtmlParser.getUrls(url), which returns a list of all URLs found on that page.

3. Stay within the same hostname - only crawl URLs that have the same hostname as the starting URL. For example, if you start at http://example.org/news, you can crawl http://example.org/sports but not http://another.com/page.

4. Avoid duplicates - each unique URL should be visited only once.

5. Return all discovered URLs in any order that belong to the same hostname.

The hostname is the domain part of the URL. For instance, in http://leetcode.com/problems, the hostname is leetcode.com. The crawler should treat URLs with and without trailing slashes as different (e.g., http://site.com and http://site.com/ are considered different URLs).

The solution uses a depth-first search (DFS) approach:

• It extracts the hostname from a URL by removing the http:// prefix (7 characters) and splitting by / to get the domain
• It maintains a set ans to track visited URLs and avoid duplicates
• For each URL, it gets all linked URLs using the HtmlParser, filters for same hostname, and recursively visits unvisited ones
• Finally, it returns all collected URLs as a list

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The web pages and their links form a graph structure. Each URL is a node, and the links between pages are edges. When a page contains links to other pages, those represent directed edges in the graph.

Is it a tree?

• No: The web structure is not a tree because:
  • Pages can have cycles (Page A can link to Page B, and Page B can link back to Page A)
  • Multiple pages can link to the same page (multiple parents)
  • There's no strict hierarchical parent-child relationship

Is the problem related to directed acyclic graphs?

• No: The web graph can contain cycles. Websites commonly have circular references where pages link back to each other.

Is the problem related to shortest paths?

• No: We're not looking for the shortest path between pages. The goal is to explore and collect all reachable URLs within the same hostname.

Does the problem involve connectivity?

• No: We're not checking if nodes are connected or finding connected components. We're performing an exhaustive exploration within a constrained domain (same hostname).

Does the problem have small constraints?

• Yes: The problem is constrained to URLs within the same hostname, which typically limits the search space. Also, we need to explore all possible paths from the starting URL.

DFS/backtracking?

• Yes: DFS is the appropriate choice because:
  • We need to explore all reachable pages systematically
  • We mark visited pages to avoid infinite loops (cycles)
  • We recursively explore each unvisited link before backtracking
  • The traversal naturally follows the link structure depth-first

Conclusion: The flowchart correctly leads us to use a DFS (Depth-First Search) approach for the web crawler problem. DFS allows us to systematically explore all pages within the same hostname while keeping track of visited URLs to avoid revisiting them.

Intuition

Think of web crawling like exploring a maze of interconnected rooms. You start in one room (the starting URL) and can see doors leading to other rooms (links to other pages). Your goal is to visit every room in your building (same hostname) exactly once, while ignoring doors that lead to other buildings (different hostnames).

The key insight is recognizing this as a graph traversal problem. Each webpage is a node, and links between pages are directed edges. Since we need to explore all reachable pages within a domain, we need a systematic way to:

1. Visit each page
2. Discover all its links
3. Follow only the valid links (same hostname)
4. Remember which pages we've already visited

DFS is a natural fit because it follows a "go as deep as possible" strategy - when you find a link, you immediately follow it, explore everything reachable from there, then backtrack. This is simpler than maintaining a queue (as in BFS) and works well since we don't care about finding the shortest path to pages, just finding all pages.

The critical observation for avoiding infinite loops is that websites often have cycles (Page A → Page B → Page A). Without tracking visited pages, we'd get stuck in these cycles forever. By maintaining a set of visited URLs, we ensure each page is processed exactly once.

The hostname extraction is straightforward: after removing the http:// prefix (7 characters), the hostname is everything before the first /. By comparing hostnames before following links, we stay within our domain boundary.

The recursive DFS structure emerges naturally: for each unvisited URL with the same hostname, we recursively apply the same exploration process. The base case is when we encounter an already-visited URL, at which point we stop to avoid redundant work.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The implementation uses a recursive DFS approach with a helper function to extract hostnames and a set to track visited URLs.

Helper Function for Hostname Extraction:

def host(url):
    url = url[7:]  # Remove "http://" (7 characters)
    return url.split('/')[0]  # Get everything before first '/'

This function extracts the hostname from a URL. For example, http://example.com/page becomes example.com.

Main DFS Function: The core exploration logic is implemented as a nested recursive function:

def dfs(url):
    if url in ans:
        return  # Base case: already visited
    ans.add(url)  # Mark as visited
    for next in htmlParser.getUrls(url):
        if host(url) == host(next):  # Same hostname check
            dfs(next)  # Recursive exploration

Algorithm Steps:

1. Initialize a set ans to store all visited URLs. Using a set ensures O(1) lookup time for checking if a URL has been visited and automatically handles duplicates.

2. Start DFS from the starting URL by calling dfs(startUrl).

3. In each DFS call:

   • Check if the current URL has been visited (base case)
   • If visited, return immediately to avoid cycles
   • If not visited, add it to the ans set
   • Get all linked URLs from the current page using htmlParser.getUrls(url)
   • For each linked URL, check if it has the same hostname
   • If the hostname matches, recursively explore that URL

4. Return the result by converting the set to a list: return list(ans)

Key Design Decisions:

• Set vs List for tracking visited URLs: A set provides O(1) membership checking compared to O(n) for a list, making the algorithm more efficient when dealing with many URLs.

• Recursive DFS vs Iterative: The recursive approach is cleaner and more intuitive for this problem. The call stack naturally handles the backtracking.

• Hostname comparison: By comparing hostnames before making the recursive call, we ensure we never explore URLs outside our domain, maintaining the problem constraints.

The time complexity is O(N + E) where N is the number of unique URLs within the hostname and E is the total number of edges (links) between them. The space complexity is O(N) for storing the visited URLs plus O(H) for the recursion stack depth, where H is the maximum depth of the URL graph.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• startUrl = "http://news.com/world"
• The HtmlParser returns the following links for each URL:
  • "http://news.com/world" → ["http://news.com/sports", "http://news.com", "http://blog.com/travel"]
  • "http://news.com/sports" → ["http://news.com/world", "http://news.com/tech"]
  • "http://news.com" → ["http://news.com/world"]
  • "http://news.com/tech" → []

Step-by-step execution:

1. Initialize: Create empty set ans = {}

2. Start DFS with "http://news.com/world":

   • Not in ans, so add it: ans = {"http://news.com/world"}
   • Get linked URLs: ["http://news.com/sports", "http://news.com", "http://blog.com/travel"]
   • Check each link:
     • "http://news.com/sports": hostname is "news.com" (same as start) → recurse
     • "http://news.com": hostname is "news.com" (same) → recurse later
     • "http://blog.com/travel": hostname is "blog.com" (different) → skip

3. DFS on "http://news.com/sports":

   • Not in ans, so add it: ans = {"http://news.com/world", "http://news.com/sports"}
   • Get linked URLs: ["http://news.com/world", "http://news.com/tech"]
   • Check each link:
     • "http://news.com/world": already in ans → skip
     • "http://news.com/tech": hostname is "news.com" (same) → recurse

4. DFS on "http://news.com/tech":

   • Not in ans, so add it: ans = {"http://news.com/world", "http://news.com/sports", "http://news.com/tech"}
   • Get linked URLs: [] (no links)
   • Nothing to explore, return

5. Back to step 2, continue with "http://news.com":

   • Not in ans, so add it: ans = {"http://news.com/world", "http://news.com/sports", "http://news.com/tech", "http://news.com"}
   • Get linked URLs: ["http://news.com/world"]
   • "http://news.com/world": already in ans → skip

6. Final result: Convert set to list and return ["http://news.com/world", "http://news.com/sports", "http://news.com/tech", "http://news.com"]

The crawler successfully found all URLs within the news.com domain while avoiding the external blog.com link and preventing infinite loops from circular references.

Solution Implementation

Time and Space Complexity

Time Complexity: O(N + E)

Where N is the total number of unique URLs within the same hostname that can be reached from the startUrl, and E is the total number of edges (links between pages).

• The DFS traversal visits each unique URL exactly once due to the check if url in ans: return, which takes O(1) time for set lookup
• For each visited URL, we call htmlParser.getUrls(url) once, which returns a list of URLs
• We iterate through all returned URLs to check if they belong to the same hostname using the host() function
• The host() function performs string operations that take O(L) time where L is the length of the URL, but this can be considered O(1) for practical URL lengths
• In total, we process each URL once and examine each edge once, resulting in O(N + E) time complexity

Space Complexity: O(N + H)

Where N is the number of unique URLs visited and H is the maximum depth of the recursion stack.

• The ans set stores all unique URLs visited within the same hostname, requiring O(N) space
• The recursive DFS call stack can go as deep as the longest path in the crawl graph, which in the worst case (a linear chain of URLs) could be O(N), but typically would be much smaller
• The space used by htmlParser.getUrls() to return lists of URLs is temporary and gets garbage collected after each call
• Converting the set to a list at the end requires O(N) additional space temporarily
• Overall space complexity is O(N) for storing the URLs plus O(H) for the recursion depth, giving us O(N + H), which simplifies to O(N) in the worst case

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Hostname Extraction for Edge Cases

The Pitfall: The current hostname extraction function assumes all URLs start with http:// and uses a fixed offset of 7 characters. This breaks if:

• URLs use https:// (8 characters)
• URLs have different protocols or formats
• The URL format is unexpected

Example failure case:

# Current implementation fails for:
url = "https://example.com/page"  # Would incorrectly parse as "s://exa..."
url = "http://example.com"  # Works, but what if no trailing path?

Solution: Use a more robust hostname extraction method:

def get_hostname(url: str) -> str:
    # Handle both http:// and https://
    if url.startswith('http://'):
        url = url[7:]
    elif url.startswith('https://'):
        url = url[8:]
  
    # Split by '/' and take hostname part
    # Handle case where there's no path after hostname
    parts = url.split('/', 1)  # Split only at first '/'
    return parts[0]

2. Stack Overflow with Deep or Cyclic URL Structures

The Pitfall: The recursive DFS approach can cause stack overflow if the URL graph is very deep or has many levels. Python's default recursion limit is around 1000, which could be exceeded in large websites.

Solution: Implement an iterative version using an explicit stack:

def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
    visited_urls = set()
    stack = [startUrl]
    start_hostname = get_hostname(startUrl)
  
    while stack:
        current_url = stack.pop()
        if current_url in visited_urls:
            continue
          
        visited_urls.add(current_url)
      
        for next_url in htmlParser.getUrls(current_url):
            if get_hostname(next_url) == start_hostname and next_url not in visited_urls:
                stack.append(next_url)
  
    return list(visited_urls)

3. Inefficient Hostname Comparison

The Pitfall: The current code calls get_hostname(current_url) inside the loop for every linked URL, even though the current URL's hostname never changes. This results in redundant parsing.

Solution: Cache the hostname calculation:

def depth_first_search(current_url: str) -> None:
    if current_url in visited_urls:
        return
  
    visited_urls.add(current_url)
    current_hostname = get_hostname(current_url)  # Calculate once
  
    for next_url in htmlParser.getUrls(current_url):
        if current_hostname == get_hostname(next_url):  # Use cached value
            depth_first_search(next_url)

4. Not Handling the Start URL's Hostname Consistently

The Pitfall: The code compares get_hostname(current_url) with get_hostname(next_url) in each recursive call, but this could lead to issues if there are redirects or if the comparison logic changes deeper in the recursion.

Solution: Store the target hostname once at the beginning:

def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
    target_hostname = get_hostname(startUrl)  # Fixed target
    visited_urls = set()
  
    def dfs(current_url: str) -> None:
        if current_url in visited_urls:
            return
        visited_urls.add(current_url)
      
        for next_url in htmlParser.getUrls(current_url):
            # Always compare against the original hostname
            if get_hostname(next_url) == target_hostname:
                dfs(next_url)
  
    dfs(startUrl)
    return list(visited_urls)

This ensures that all URLs are compared against the same reference hostname throughout the crawling process, preventing drift or inconsistencies.