Python 中查找通过一次交换得到的最小的字典序字符串的程序

假设我们有一个字符串 s，我们需要找到通过最多交换两个字符可以得到的字典序最小的字符串。

因此，如果输入为 "zyzx"，则输出将为 "xyzz"

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

  • temp := 一个大小为 s 的数组，并用 0 填充
  • m:= s 的大小 - 1
  • 对于 i 在 s 的大小 -1 到 -1 的范围内，递减 1，执行以下操作：
    • 如果 s[i] < s[m]，则
      • m := i
    • temp[i] := m
    • 对于 i 在 0 到 s 的大小的范围内，执行以下操作：
      • a := temp[i]
      • 如果 s[a] 与 s[i] 不相同，则
        • 返回 s 的子字符串（从索引 0 到 i）连接 s[a] 连接 s 的子字符串（从索引 i+1 到 a）连接 s[i] 连接 s 的子字符串（从索引 a+1 到结尾）
  • 返回 s

示例

 实时演示

class Solution:
   def solve(self, s):
      temp = [0]*len(s)
      m=len(s)-1
      for i in range(len(s)-1, -1, -1):
         if s[i]<s[m]: m=i
            temp[i] = m
      for i in range(len(s)):
         a = temp[i]
         if s[a] != s[i]:
            return s[:i]+s[a]+s[i+1:a]+s[i]+s[a+1:]
      return s
ob = Solution()
print(ob.solve("zyzx"))

输入

zyzx

输出

xyzz

更新于: 2020-10-06

3K+ 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告