Web Crawler Python Solution with Tests

Tested Python solution for LeetCode 1236 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 1236, Medium. Topics: Depth-First Search, Breadth-First Search, String, Interactive. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 18 parametrized pytest cases, and a playground notebook:

lcpy gen -n 1236   # by problem number
lcpy gen -s web_crawler   # by problem name

​

Problem

Given a url startUrl and an interface HtmlParser, implement a web crawler to crawl all links that are under the same hostname as startUrl.

Return all urls obtained by your web crawler in any order.

Your crawler should:

• Start from the page: startUrl
• Call HtmlParser.getUrls(url) to get all urls from a webpage of given url.
• Do not crawl the same link twice.
• Explore only the links that are under the same hostname as startUrl.

As shown in the example url above, the hostname is example.org. For simplicity sake, you may assume all urls use http protocol without any port specified. For example, the urls http://leetcode.com/problems and http://leetcode.com/contest are under the same hostname, while urls http://example.org/test and http://example.com/abc are not under the same hostname.

The HtmlParser interface is defined as such:

interface HtmlParser {
  // Return a list of all urls from a webpage of given url.
  public List<String> getUrls(String url);
}

Below are two examples explaining the functionality of the problem, for custom testing purposes you’ll have three variables urls, edges and startUrl. Notice that you will only have access to startUrl in your code, while urls and edges are not directly accessible to you in code.

Note: Consider the same URL with the trailing slash / as a different URL. For example, http://news.yahoo.com, and http://news.yahoo.com/ are different urls.

​

Examples

Input:
urls = [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.google.com",
  "http://news.yahoo.com/us"
]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl = "http://news.yahoo.com/news/topics/"
Output:
[
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.yahoo.com/us"
]

Input:
urls = [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.google.com"
]
edges = [[0,2],[2,1],[3,2],[3,1],[3,0]]
startUrl = "http://news.google.com"
Output: ["http://news.google.com"]
Explanation: The startUrl links to all other pages that do not share the same hostname.

​

Constraints

• 1 <= urls.length <= 1000
• 1 <= urls[i].length <= 300
• startUrl is one of the urls.
• Hostname label must be from 1 to 63 characters long, including the dots, may contain only the ASCII letters from ‘a’ to ‘z’, digits from ‘0’ to ‘9’ and the hyphen-minus character (’-’).
• The hostname may not start or end with the hyphen-minus character (’-’).
• You may assume there’re no duplicates in url library.

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class HtmlParser:
    # Test-harness API: backs the getUrls interface with the url library
    def __init__(self, urls: list[str], edges: list[list[int]]) -> None:
        self.adj: dict[str, list[str]] = {u: [] for u in urls}
        for a, b in edges:
            self.adj[urls[a]].append(urls[b])

    def get_urls(self, url: str) -> list[str]:
        return self.adj[url]


class Solution:
    # Time: O(V + E) pages and links visited once
    # Space: O(V) visited set
    def crawl(self, start_url: str, html_parser: HtmlParser) -> list[str]:
        host = start_url[7:].split("/")[0]
        visited = {start_url}
        stack = [start_url]
        while stack:
            url = stack.pop()
            for link in html_parser.get_urls(url):
                if link in visited or link[7:].split("/")[0] != host:
                    continue
                visited.add(link)
                stack.append(link)
        return list(visited)

​

Complexity

Time	Space
O(V + E) pages and links visited once	O(V) visited set

​

Tags

NeetCode All.