Web Crawler — LeetCode 1236 Python Solution
MediumLeetCode PremiumDepth-First SearchBreadth-First SearchStringInteractive
- Problem
- #1236
- Pattern
- Breadth-First Search
- Reading time
- 5 min
- Source
- leetcode.com
The 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.
Example
interface HtmlParser {
// Return a list of all urls from a webpage of given url.
public List<String> getUrls(String url);
}Python solution
Python
# """
# This is HtmlParser's API interface.
# You should not implement it, or speculate about its implementation
# """
# class HtmlParser(object):
# def getUrls(self, url):
# """
# :type url: str
# :rtype List[str]
# """
class Solution:
def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
def host(url):
url = url[7:]
return url.split('/')[0]
def dfs(url):
if url in ans:
return
ans.add(url)
for next in htmlParser.getUrls(url):
if host(url) == host(next):
dfs(next)
ans = set()
dfs(startUrl)
return list(ans)Complexity
| Measure | Complexity |
|---|---|
| Time | O(V+E) |
| Space | O(V) auxiliary |
Pattern: Breadth-First Search
Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 1236. Web Crawler is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.
The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1236. Web Crawler?
- LeetCode 1236. Web Crawler is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1236. Web Crawler?
- The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 1236. Web Crawler?
- The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 1236. Web Crawler cover?
- LeetCode 1236. Web Crawler is tagged Depth-First Search, Breadth-First Search, String and Interactive on LeetCode.
- Is LeetCode 1236. Web Crawler a premium problem?
- Yes. LeetCode 1236. Web Crawler is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.