535. Encode and Decode TinyURL - Explanation

1. List

class Codec:

    def __init__(self):
        self.urls = []

    def encode(self, longUrl: str) -> str:
        self.urls.append(longUrl)
        return 'http://tinyurl.com/' + str(len(self.urls) - 1)

    def decode(self, shortUrl: str) -> str:
        return self.urls[int(shortUrl.split('/')[-1])]

Time & Space Complexity

Time complexity: $O(1)$ for $encode()$ and $decode()$ .
Space complexity: $O(n * m)$

Where $n$ is the number of $longUrls$ , $m$ is the average length of the URLs.

2. Hash Map - I

class Codec:

    def __init__(self):
        self.url_map = {}
        self.id = 0

    def encode(self, longUrl: str) -> str:
        self.url_map[self.id] = longUrl
        short_url = f"http://tinyurl.com/{self.id}"
        self.id += 1
        return short_url

    def decode(self, shortUrl: str) -> str:
        url_id = int(shortUrl.split('/')[-1])
        return self.url_map[url_id]

Time & Space Complexity

Time complexity: $O(1)$ for $encode()$ and $decode()$ .
Space complexity: $O(n * m)$

Where $n$ is the number of $longUrls$ , $m$ is the average length of the URLs.

3. Hash Map - II

class Codec:

    def __init__(self):
        self.encodeMap = {}
        self.decodeMap = {}
        self.base = "http://tinyurl.com/"

    def encode(self, longUrl: str) -> str:
        if longUrl not in self.encodeMap:
            shortUrl = self.base + str(len(self.encodeMap) + 1)
            self.encodeMap[longUrl] = shortUrl
            self.decodeMap[shortUrl] = longUrl
        return self.encodeMap[longUrl]

    def decode(self, shortUrl: str) -> str:
        return self.decodeMap[shortUrl]

Time & Space Complexity

Time complexity: $O(1)$ for $encode()$ and $decode()$ .
Space complexity: $O(n * m)$

Where $n$ is the number of $longUrls$ , $m$ is the average length of the URLs.