Chương trình tìm số mảng vuông trong Python

Giả sử chúng ta muốn tạo một chuỗi đích gồm các chữ cái thường. Lúc đầu, chúng ta có dãy là n '?' dấu (n là độ dài của chuỗi đích). Chúng tôi cũng có một con dấu của chữ thường. Trên mỗi lượt, chúng ta có thể đặt con tem trên dãy và thay thế mọi chữ cái trong con dấu bằng chữ cái tương ứng từ con tem đó. Bạn có thể thực hiện tối đa 10 * n lượt.

Ví dụ, hãy xem xét chuỗi ban đầu là "?????" và dấu là "abc", sau đó chúng ta có thể tạo các chuỗi như "abc ??", "? Abc?", "?? abc" trong đầu tiên xoay. Nếu chuỗi có thể được đóng dấu, thì trả về một mảng của chỉ số với chữ cái ngoài cùng bên trái được đóng dấu ở mỗi lượt. Nếu không được thì trả về một mảng trống. Vì vậy, khi dãy là "ababc" và dấu là "abc", thì câu trả lời có thể giống như [0, 2], Bởi vì chúng ta có thể tạo thành như "?????" -> "abc ??" -> "ababc".

Vì vậy, nếu đầu vào là s =​​"abcd" t ="abcdbcd", thì đầu ra sẽ là [3,0]

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

• nếu kích thước của s bằng 1 thì

  • trả về danh sách từ 0 đến t khi tất cả các ký tự trong t đều giống nhau và chúng là s [0], nếu không sẽ là danh sách trống mới

• ans:=một danh sách mới

• trong khi t không giống với kích thước của t số "?" đánh dấu, làm

  • tmp:=t

  • đối với tôi trong phạm vi từ 0 đến kích thước của s, thực hiện

    • cho j có kích thước từ s xuống đến i + 1:

      • tìm kiếm:=i number of "?" nối chuỗi con của s [từ chỉ số i đến j-1] nối (kích thước của s - j) số "?"

      • trong khi tìm kiếm trong t, hãy làm

        • chèn nơi tìm kiếm hiện diện trong t ở cuối ans

        • t:=thay thế tìm kiếm bằng kích thước của s số "?" chỉ một lần

      • nếu t giống với kích thước của t số "?", thì

        • đi ra từ vòng lặp

      • nếu t giống với kích thước của t số "?", thì

        • đi ra từ vòng lặp

    • nếu tmp giống với t, thì

      • đi ra từ vòng lặp

• trả về đảo ngược của ans.

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn

def solve(s, t):
   if len(s) == 1:
      return [i for i in range(len(t))] if all(t==s[0] for t in t)else []

   ans = []
   while t != "?" * len(t):
      tmp = t
      for i in range(len(s)):
         for j in reversed(range(i+1, len(s)+1)):
            search = "?" * i + s[i:j] + "?" * (len(s)-j)
            while t.find(search) != -1:
               ans.append(t.find(search))
               t = t.replace(search, "?"*len(s), 1)
            if t == "?" * len(t): break
         if t == "?" * len(t): break
      if tmp == t: return []
   return ans[::-1]

s = "abcd"
t = "abcdbcd"
print(solve(s, t))

Đầu vào

"abcd", "abcdbcd"

Đầu ra

[3,0]