Chương trình tìm chuỗi nhỏ nhất theo ngôn ngữ học với một lần hoán đổi trong Python

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm chuỗi nhỏ nhất về mặt từ vựng có thể được tạo ra nếu chúng ta có thể thực hiện nhiều nhất một lần hoán đổi giữa hai ký tự trong chuỗi s đã cho.

Vì vậy, nếu đầu vào là "zyzx", thì đầu ra sẽ là "xyzz"

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• temp:=một mảng có kích thước s và điền bằng 0
• m:=kích thước của s - 1
• đối với tôi trong phạm vi kích thước từ s -1 đến -1, giảm đi 1, thực hiện
  • nếu s [i]
  • m:=i
• temp [i]:=m
• đối với tôi trong phạm vi từ 0 đến kích thước của s, thực hiện
  • a:=temp [i]
  • nếu s [a] không giống với s [i], thì
    • trả về chuỗi con của s [từ chỉ số 0 đến i] chuỗi con nối của s [a] chuỗi con nối của s [từ chỉ số i + 1 đến a] chuỗi con nối của s [i] chuỗi con nối của s [từ chỉ số a + 1 đến cuối]

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