codewars URLshortener

URL shortener

题目要求：

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

有两种思路：

1. index转26进制 §

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

$$25\ast 26^3+25\ast 26^2+25\ast 26^1+26=456976<475000$$

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

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

$$26^4+26^3+26^2+26=475254>475000$$

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

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