0%

codewars URLshortener

Posted on Edited on In
Symbols count in article: 1.3k Reading time ≈ 1 mins.

CodeWars - HackMD

URL shortener

题目要求：

  1. 475,000个测试用例
  2. 只能使用 26 个小写字母
  3. 短链长度为 4

有两种思路：

1. index转26进制

令a=0a=0, 此时除0的情况外, a不能出现在首位, 长度为4的26进制的情况数有

25∗263+25∗262+25∗261+26=456976<47500025*26^3+25*26^2+25*26^1+26 = 456976 < 475000

2. index与可重复全排列双射

此时a没有数学意义，可以出现在首位，所以情况数为

264+263+262+26=475254>47500026^4+26^3+26^2+26=475254>475000

这里在参考康托展开和逆康托展开就可以得到index和short url之间的转化关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
base = 26
BASE = [0]
index = 0
table = [""]
hash_table = {}


def init():
    for i in range(6):
        BASE.append(BASE[len(BASE)-1]+base**i)


def get_N(x):
    for i in range(len(BASE)):
        if BASE[i] <= x and BASE[i+1] > x:
            return i


def cantor(x):
    # short to index
    result = 0
    for i in range(len(x)):
        result += (ord(x[i])-ord('a')) * base**(len(x) - i - 1)
    return result + BASE[len(x)]


def re_cantor(x):
    # index to short
    n = get_N(x)
    x -= BASE[n]
    result = ""
    for i in range(n):
        tmp = x // (base ** (n-i-1))
        result = result + chr(ord('a') + tmp)
        x -= tmp * (base ** (n-i-1))
    return result


init()


def url_shortener(long_url):
    global index
    if long_url not in hash_table:
        index = index + 1
        table.append(long_url)
        short_url = re_cantor(index)
        hash_table[long_url] = short_url
    else:
        print(long_url)
        short_url = hash_table[long_url]
    return 'short.ly/'+short_url

def url_redirector(short_url):
    long_url = table[cantor(short_url[9:])]
    return long_url