Xóa cột để mảng chuỗi được sắp xếp trong Python

Giả sử ta có mảng N chuỗi chữ thường, tên mảng A, tất cả chuỗi cùng độ dài. Ta chọn tập chỉ số xóa, và với mỗi chuỗi, xóa tất cả ký tự ở những chỉ số đó.

Ví dụ, A = ["abcdef","uvwxyz"] và chỉ số xóa {0,2,3}, mảng sau xóa là ["bef", "vyz"], các cột còn lại là ["b","v"], ["e","y"], ["f","z"].

Giả sử ta chọn tập chỉ số xóa D sao cho sau xóa, mỗi cột còn lại trong A theo thứ tự không giảm. Ta tìm giá trị nhỏ nhất có thể của độ dài D.

Ví dụ, đầu vào ["cba","daf","ghi"], đầu ra 1, vì chọn D={1}, cột ["c","d","g"] và ["a","f","i"] không giảm. Nếu D={}, cột ["b","a","h"] không không giảm.

Giải quyết:

• A := ma trận từ mảng chuỗi, tách ký tự thành cột
• B := list rỗng
• for col in A, do
  • if col đã sắp xếp thì thêm 0 vào B
  • ngược lại thêm 1 vào B
• trả về tổng các phần tử B

Xem triển khai:

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"]

Đầu ra

1