⚡Flashcard Drill➔
NeetCode #607LC-1236MediumGraphsNC Algo100
← Back to All Problems

#607 · #1236 · Web Crawler(网络爬虫)

📌 Problem Statement & Constraints

This is an interactive problem. Given a startUrl and an HtmlParser with getUrls(url) returning the links on a page, return all URLs reachable from startUrl that share its hostname. Constraints: at most 10^4 URLs; total content at most 10^6 characters.

💡 Core Algorithmic Approaches

  1. A standard BFS/DFS over the link graph, filtered by hostname.
  2. The hostname is the substring up to the first / after the protocol; comparing it requires parsing.
  3. Only follow links whose hostname matches the start URL's.
  4. A visited set prevents infinite loops.

💻 Benchmark Python3 Implementation

class Solution:
    def crawl(self, startUrl: str, htmlParser: "HtmlParser") -> List[str]:
        from collections import deque
        # hostname = everything up to the first '/' after "://"
        host = startUrl[:startUrl.find("/", 8)]
        seen = {startUrl}
        q = deque([startUrl])
        while q:
            url = q.popleft()
            for nxt in htmlParser.getUrls(url):
                if nxt not in seen and nxt.startswith(host):
                    seen.add(nxt)
                    q.append(nxt)
        return list(seen)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(total content + number of URLs): each page is parsed once.
💾 Space Complexity
O(number of URLs) for the visited set and the queue.

⚠️ Interview Pitfalls & Follow-ups

  • Using startswith(startUrl): that filters by path prefix, not hostname; "http://news.yahoo.com" and "http://news.yahoo.com.cn" would be confused.
  • Extracting the hostname with a naive split: url.split("/")[2] is the usual approach; the find variant used here avoids the leading empty segment.
  • Forgetting the visited set: cycles would loop forever.
  • Parsing the HTML yourself: the HtmlParser API already extracts the links.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems