Can anyone help me to understand the question?


  • 4
    Z

    The questions states:
    Note: Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.

    Maybe I misunderstand the question, but does it means we are not allowed to use hashtable/database to store the original and shortened url? As I understand the url shortening services are rely on database and cache to store the hash to the original url, otherwise this is more like a string compression algorithm.

    Any comments are highly appreciated.


  • 0
    N

    Yes, stateless means you cannot store or identify any previous url. However, the use of state is not detectable in the submission. As you mentioned, you can use loseless string compression for this problem.


  • 0
    Z

    @niwota But how can we guarantee the compressed url is always shorter than the original url without loss data?


  • 0
    Z

    @zhongyuan9817 take the shorter


  • 0
    Q

    Don't think there exist one way by data compression. if there exist, it's not a shorten url. As we all know, shorten url is something like signature, not compression. compression never gurrantee the compression rate.

    public class Codec {
        List<String> urls = new ArrayList<String>();
        // Encodes a URL to a shortened URL.
        public String encode(String longUrl) {
            urls.add(longUrl);
            return String.valueOf(urls.size()-1);
        }
    
        // Decodes a shortened URL to its original URL.
        public String decode(String shortUrl) {
            int index = Integer.valueOf(shortUrl);
            return (index<urls.size())?urls.get(index):"";
        }
    }
    

  • 0
    Z

    @qiu5 Yeah, that's why I ask this question :)


  • 3

    I'm pretty sure it's a mistake. Probably someone copied the Encode and Decode Strings problem and didn't realize that that note should be rewritten. The intention is that we must not do something like this:

    public class Codec {
        String theLatestUrl;
        public String encode(String longUrl) {
            theLatestUrl = longUrl;
            return "whatever, doesn't matter";
        }
        public String decode(String shortUrl) {
            return theLatestUrl;
        }
    }
    

    That is obviously not a legitimate solution. But using a "database" is.


  • 0
    Z

    @StefanPochmann yeah, the expected solution should convert some auto incremented id (database id) to a short string.


  • 0

    @StefanPochmann Yeah it was a mistake. I have removed that note now.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.