在 Python 中查找给定两个字符串之间的字典序字符串

假设我们有两个字符串 S 和 T，我们需要检查是否存在一个与 S 和 T 长度相同的字符串，并且该字符串在字典序上大于 S 且小于 T。如果不存在这样的字符串，则返回 -1。我们需要记住，S = S1S2… Sn 在字典序上小于 T = T1T2… Tn，当且仅当存在一个 i，使得 S1= T1，S2= T2，… Si – 1= Ti – 1，Si < Ti。

因此，如果输入像 S = "bbb" 和 T = "ddd"，则输出将是 "bbc"

为了解决这个问题，我们将遵循以下步骤：

  • n := 字符串的大小
  • 对于 i 从 n - 1 到 0，递减 1，执行：
    • 如果字符串[i] 不等于 'z'，则：
      • k := 字符串[i] 的 ASCII 码
      • 字符串[i] := 来自 ASCII 码 (k + 1) 的字符
      • 连接字符串字符并返回
    • 字符串[i] := 'a'

示例

让我们看看下面的实现来更好地理解：

 在线演示

def find_next(string):
   n = len(string)
   for i in range(n - 1, -1, -1):
      if string[i] != 'z':
         k = ord(string[i])
         string[i] = chr(k + 1)
         return ''.join(string)
      string[i] = 'a'
S = "bbb"
T = "ddd"
S = list(S)
res = find_next(S)
if res != T:
   print(res)
else:
   print(-1)

输入

"bbb", "ddd"

输出

bbc

更新于: 2020-08-28

217 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告