福
福

雨辰枫司的小栈

最小表示法

  • 659 字
  • 条评论

最小表示法

一个字符串的字典序最小表示

先复制一遍字符串添加在后面(字符串环的操作)
初始化 , 用来表示当前能表示字典序最小的开始下标当 与 不相等时 替换较大的那个 即 或
循环到最后选出,最小值即为最小表示法的开始坐标即为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def getMinDenote(s:str) -> str:
    lens = len(s)
    word = list(s) + list(s)
    i,j = 0, 1
    while i < lens and j < lens:
        k = 0
        while k < lens and word[i + k] == word[j + k]:
            k += 1
        if k == lens:
            break
        if word[i + k] > word[j + k]:
            i += (k + 1)
            if i == j:
                i += 1
        else:
            j += (k + 1)
            if i == j:
                j += 1
    mind = min(i,j)
    return ''.join(word[mind:mind+lens])
,