杂谈：经典算法之字典序排列

• 杂谈：经典算法之字典序排列
  • 0. 引言
  • 1. 字典序排序
  • 2. 获取字典序排列的邻接元素
    • 1. 获取字典序排序的次小字符串
    • 2. 获取字典序排序的次大字符串
  • 3. 参考链接

0. 引言

最近连着两周打比赛都遇到了字符串字典序的相关问题，然后还连着两周都在这个坑里面摔死，简直了……

因此，就趁着这个假期来整理一下字典序相关的内容，省的后面再在同一个问题上摔倒了……

1. 字典序排序

我们首先来看一下字典序排序的定义。

考察两个字符串s以及s'，s字典序在s'之前的判断条件为：

def is_smaller(s1, s2):
    n, m = len(s1), len(s2)
    i = 0
    while i < n and i < m:
        if s1[i] == s2[i]:
            i += 1
        elif s1[i] < s2[i]:
            return True
        else:
            return False
    return i == n and i < m

可以看到：

1. 字典序下的两个字符串之间的大小关系取决于第一个不同的元素，哪个元素小则其对应的字符串的字典序更小；
2. 如果某一字符串是另一个字符串的前缀字符串，那么其字典序小于后者；

2. 获取字典序排列的邻接元素

现在，我们来看如何来获取字典序排列的邻接字符串，即按照字典序排序的次大或者次小字符串。

1. 获取字典序排序的次小字符串

我们首先以字典序排序的次小字符串的次小字符串为例进行考察。

显而易见的，它必然要求我们将字符串中的某一个元素替换为后续字符串中某一个比它更小的字符，而这个字符必须是后方字符中最靠近该字符的一个，然后，我们需要需要对后方字符进行调整，使得其按照顺序排列，确保它是最大的那个子串。

leetcode的1830题当中给出了一种制式化但是简单直接的获取过程，即：

1. 找到 最大下标 i ，使得 1 <= i < s.length 且 s[i] < s[i - 1] 。
2. 找到 最大下标 j ，使得 i <= j < s.length 且对于所有在闭区间 [i, j] 之间的 k 都有 s[k] < s[i - 1] 。
3. 交换下标为 i - 1​​​​ 和 j​​​​ 处的两个字符。
4. 将下标 i 开始的字符串后缀反转。

换用代码语言即：

def get_next(s):
    n = len(s)
    i = n-1
    while i > 0 and s[i] >= s[i-1]:
        i -= 1
    j = i
    while j < n and s[j] < s[i-1]:
        j += 1
    j -= 1
    s = s[:i-1] + s[j] + (s[i:j] + s[i-1] + s[j+1:])[::-1]
    return s

而关于上述方法为什么在逻辑上是可行的，这个事实上也是比较显然的。

根据步骤1，显然从下标i开始的后续子串是递增的，而根据步骤2，s[j]是子串s[i:]之后当中小于s[i-1]的最大字符，交换s[i-1]与s[j]之后，显然字符串在字典序上变小了，且s[i:]依然保持有序，此时再将s[i:]进行倒序操作，就能够获取前缀为s[:i]时的子串的最大字典序子串，即之前一个子串的次小字典序子串。

2. 获取字典序排序的次大字符串

我们仿照上述获取次小字符串的方法，同样可以给出制式化的获取次大字符串的步骤如下：

1. 找到 最大下标 i ，使得 1 <= i < s.length 且 s[i] > s[i - 1] 。
2. 找到 最大下标 j ，使得 i <= j < s.length 且对于所有在闭区间 [i, j] 之间的 k 都有 s[k] > s[i - 1] 。
3. 交换下标为 i - 1​​​​ 和 j​​​​ 处的两个字符。
4. 将下标 i 开始的字符串后缀反转。

同样可以给出代码实现如下：

def get_next(s):
    n = len(s)
    i = n-1
    while i > 0 and s[i] <= s[i-1]:
        i -= 1
    j = i
    while j < n and s[j] > s[i-1]:
        j += 1
    j -= 1
    s = s[:i-1] + s[j] + (s[i:j] + s[i-1] + s[j+1:])[::-1]
    return s

3. 参考链接

1. 1830. 使字符串有序的最少操作次数
2. 31. 下一个排列