Сложность: 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 {
func getUrls(_ url: String) -> [String] {
return []
}
}
func extractHostname(_ url: String) -> String {
if let host = URL(string: url)?.host {
return host
}
return ""
}
func crawl(_ startUrl: String, _ htmlParser: HtmlParser) -> [String] {
let hostname = extractHostname(startUrl)
var visited = Set<String>()
var queue = [startUrl]
visited.insert(startUrl)
while !queue.isEmpty {
let url = queue.removeFirst()
for nextUrl in htmlParser.getUrls(url) {
if !visited.contains(nextUrl) && extractHostname(nextUrl) == hostname {
visited.insert(nextUrl)
queue.append(nextUrl)
}
}
}
return Array(visited)
}Ставь 👍 и забирай 📚 Базу знаний