Mid/Senior
Web Crawler
You are given a list of web page URLs and a directed link graph. Each URL uses the format http://hostname/path, and the hostname is the substring after http:// and before the next /.
The array urls contains every page in the graph. Each directed edge edges[i] = [from, to] means that the page urls[from] contains a link to the page urls[to]; this simulates what a web crawler would discover from HtmlParser.getUrls(url).
Given start_url, crawl all pages reachable from start_url by repeatedly following links, but only include and continue crawling pages whose hostname is the same as the hostname of start_url.
Return all crawled URLs in any order.
Rules:
- You should not visit the same URL more than once.
- You must not crawl or return URLs with a different hostname from
start_url.
Example 1
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]], start_url = "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"]Starting from the topics page, the crawler can reach the Yahoo pages at indices 0, 1, 2, and 4, all of which share the hostname
news.yahoo.com.Example 2
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 = [[0,2],[2,1],[3,2],[3,1],[0,4]], start_url = "http://news.yahoo.com/news/topics/"Output
["http://news.yahoo.com/news","http://news.yahoo.com/news/topics/"]From the starting URL, only the news page is reachable with the same hostname, so the crawler returns those two Yahoo URLs.
Constraints
- 1 <= urls.length <= 1000
- 1 <= urls[i].length <= 300
- All urls are unique
- 0 <= edges.length <= urls.length * (urls.length - 1)
- edges[i].length == 2
- 0 <= edges[i][0], edges[i][1] < urls.length
- startUrl is one of urls
- All URLs use the http protocol and do not contain a port, query string, or fragment
- Each hostname has length from 1 to 63 characters