Problem Breakdown
The problem requires traversing a directed graph where nodes are URLs and edges represent hyperlinks found via HtmlParser.getUrls. The core constraints are:
- Hostname Filtering: Only visit links that share the exact hostname (domain) of the starting URL. Paths, query parameters, or ports must be ignored for matching purposes.
- Cycle Prevention & Deduplication: Web graphs often contain cycles and multiple paths to the same page. We must ensure each valid URL is processed exactly once using a
visitedset. - Traversal Order: The problem allows returning URLs in any order, so Depth-First Search (DFS) or Breadth-First Search (BFS) are both acceptable choices for traversal logic.
Intuition
This is a graph exploration problem with specific filtering constraints.
- We start at
startUrland extract its hostname to establish the target domain. - For every URL we visit, we fetch all outgoing links (
getUrls). - Each link must be checked against two conditions:
- Does it belong to the same hostname? (Hostname parsing).
- Have we already visited this specific URL? (Visited set check).
- If both are true, we add the new URL to our collection and mark it as visited before pushing onto the stack/queue. Marking upon discovery prevents duplicate entries in the traversal structure, optimizing space complexity compared to checking on pop.
Approach
- Hostname Extraction: Create a helper function that parses
http://hostname/pathinto justhostname. Since ports are not specified per constraints, we look for the substring starting after//and ending at the next/. - Initialization:
- Parse
startUrlto gettarget_hostname. - Initialize a stack (for DFS) or queue with
startUrl. - Maintain a set of visited URLs initialized with
startUrl. This ensures we don’t process the start node multiple times if it appears as its own link.
- Parse
- Traversal:
- While the traversal structure is not empty, pop/peek current URL.
- Call
getUrlsto get neighbors. - Iterate through neighbors: Check hostname match and visited status. If valid and unvisited, add to stack and mark as visited immediately.
- Result: Convert the set of visited URLs into a list for return.
Complexity Analysis
- Time Complexity: , where is the number of reachable nodes under the hostname constraint (valid crawled pages), and is the average length of a URL string required for parsing hostnames. Each edge in the valid subgraph is processed once because we mark nodes as visited immediately upon discovery.
- Space Complexity: to store the
visitedset, which contains all unique URLs found under the same hostname, and the stack/queue used for traversal.
Solution
class Solution:
def crawl(self, startUrl):
# Helper function to extract hostname from URL string
# assuming http:// protocol without port specified (per problem constraints)
def get_hostname(url):
idx = url.find('//') + 2
if idx >= len(url):
return ""
slash_idx = url.find('/', idx)
end_idx = slash_idx if slash_idx != -1 else len(url)
return url[idx:end_idx]
target_hostname = get_hostname(startUrl)
# Visited set tracks all valid URLs found under the same hostname.
visited = {startUrl}
stack = [startUrl]
while stack:
curr_url = stack.pop()
try:
neighbors = HtmlParser.getUrls(curr_url)
except Exception:
continue
for neighbor in neighbors:
# Check if not visited first to avoid redundant hostname parsing and checks
if neighbor not in visited:
hostname = get_hostname(neighbor)
# Only crawl if same hostname matches startUrl's hostname
if hostname == target_hostname:
stack.append(neighbor)
visited.add(neighbor)
return list(visited)
Edge Cases Handled
- **Start URL with