Сложность: medium
Учитывая url startUrl и интерфейс HtmlParser, реализуйте веб-краулер для просмотра всех ссылок, которые находятся под тем же именем хоста, что и startUrl.Верните все ссылки, полученные вашим краулером, в любом порядке. Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все ссылки с веб-страницы с заданным url. Не просматривайте одну и ту же ссылку дважды. Исследуйте только те ссылки, которые находятся под тем же именем хоста, что и startUrl. Как показано в примере url выше, имя хоста - example.org. Для простоты можно считать, что все урлы используют протокол http без указания порта. Например, урлы http://leetcode.com/problems и http://leetcode.com/contest находятся под одним и тем же именем хоста, а урлы http://example.org/test и http://example.com/abc не находятся под одним и тем же именем хоста.
Пример:
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"
]
👨💻 Алгоритм:
1⃣Извлечение имени хоста:
Сначала извлекаем имя хоста из начального URL для проверки всех последующих ссылок.
2⃣Использование очереди для BFS:
Начинаем с начального URL и помещаем его в очередь.
Пока очередь не пуста, извлекаем текущий URL, получаем все ссылки с этой страницы, и для каждой ссылки проверяем, принадлежит ли она тому же имени хоста.
3⃣Если да, и если мы еще не посещали эту ссылку, добавляем ее в очередь и отмечаем как посещенную.
😎 Решение:
class HtmlParser:
def getUrls(self, url: str) -> [str]:
pass
def extractHostname(url):
from urllib.parse import urlparse
parsed_url = urlparse(url)
return parsed_url.netloc
def crawl(startUrl: str, htmlParser: HtmlParser) -> [str]:
from collections import deque
hostname = extractHostname(startUrl)
visited = set()
queue = deque([startUrl])
visited.add(startUrl)
while queue:
url = queue.popleft()
for next_url in htmlParser.getUrls(url):
if next_url not in visited and extractHostname(next_url) == hostname:
visited.add(next_url)
queue.append(next_url)
return list(visited)
Ставь 👍 и забирай 📚 Базу знаний