Xóa các cột để sắp xếp bằng Python

Giả sử chúng ta có một mảng gồm N chuỗi ký tự viết thường, tên mảng là A, tất cả các chuỗi đều có cùng độ dài. Bây giờ, chúng tôi có thể chọn bất kỳ tập hợp chỉ số xóa nào và đối với mỗi chuỗi, chúng tôi xóa tất cả các ký tự trong các chỉ số đó.

Ví dụ:nếu chúng ta có một mảng A như ["abcdef", "uvwxyz"] và chỉ số xóa là {0, 2, 3}, thì mảng cuối cùng sau khi xóa sẽ là ["bef", "vyz"], và các cột còn lại của A là ["b", "v"], ["e", "y"] và ["f", "z"].

Giả sử chúng ta đã chọn một tập hợp các chỉ số xóa D như sau khi xóa, mỗi cột còn lại trong A có thứ tự được sắp xếp không giảm. Chúng ta phải tìm giá trị nhỏ nhất có thể có của độ dài D.

Vì vậy, nếu đầu vào là ["cba", "daf", "ghi"], thì đầu ra sẽ là 1, điều này là do sau khi chọn D ={1}, thì mỗi cột ["c", "d" , "g"] và ["a", "f", "i"] theo thứ tự sắp xếp không giảm. Và nếu chúng tôi chọn D ={}, thì cột ["b", "a", "h"] sẽ không có thứ tự không giảm dần.

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

A =tạo ma trận bằng cách lấy các chuỗi từ mảng và phân tách các ký tự thành cột khác nhau
B =danh sách trống mới
for col in A, do
- nếu col đã được sắp xếp thì hãy chèn 0 vào B
- nếu không thì chèn 1 vào B
trả về tổng của tất cả các phần tử trong B

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

Ví dụ

class Solution:
   def minDeletionSize(self, A):
      return sum([1-(sorted(col)==list(col)) for col in zip(*A)])
ob = Solution()
print(ob.minDeletionSize(["cba","daf","ghi"]))

Đầu vào

["cba","daf","ghi"]

Xóa các cột để sắp xếp bằng Python

Ví dụ

Đầu vào

Đầu ra