用 Python 编写程序，通过一次交换找到字典顺序最小的字符串

pythonserver side programmingprogramming更新于 2026/1/10 18:20:17

假设我们有一个字符串 s，我们必须找到字典顺序最小的字符串，如果我们可以在给定字符串 s 中的两个字符之间进行最多一次交换。

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

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

temp := 大小为 s 的数组并用 0 填充
m:= s 的大小 - 1
对于 i，在 s 的大小范围 -1 到 -1 内，减少 1，执行
- 如果 s[i] < s[m]，则
  - m := i
- temp[i] := m
- 对于范围从 0 到 s 大小的 i，执行
  - 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"))