สมมติว่าเรามีอาร์เรย์ของสตริงอักษรตัวพิมพ์เล็ก N ชื่ออาร์เรย์คือ A สตริงทั้งหมดมีความยาวเท่ากัน ตอนนี้ เราสามารถเลือกชุดของดัชนีการลบ และสำหรับแต่ละสตริง เราจะลบอักขระทั้งหมดในดัชนีเหล่านั้น
ตัวอย่างเช่น หากเรามีอาร์เรย์ A เช่น ["abcdef","uvwxyz"] และดัชนีการลบคือ {0, 2, 3} ดังนั้นอาร์เรย์สุดท้ายหลังการลบจะเป็น ["bef", "vyz"], และคอลัมน์ที่เหลือของ A คือ ["b","v"], ["e","y"] และ ["f","z"]
สมมติว่าเราเลือกชุดของดัชนีการลบ D เช่นเดียวกับหลังการลบ คอลัมน์ที่เหลือใน A แต่ละรายการจะเรียงลำดับแบบไม่ลดลง เราต้องหาค่าต่ำสุดที่เป็นไปได้ของความยาวของ D
ดังนั้น หากอินพุตเป็น ["cba","daf","ghi"] ผลลัพธ์จะเป็น 1 เนื่องจากหลังจากเลือก D ={1} แล้วแต่ละคอลัมน์ ["c","d" ,"g"] และ ["a","f","i"] อยู่ในการเรียงลำดับที่ไม่ลดลง และถ้าเราเลือก D ={} คอลัมน์ ["b","a","h"] จะไม่อยู่ในลำดับที่ไม่เรียงลำดับ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- A =สร้างเมทริกซ์โดยนำสตริงจากอาร์เรย์และแยกอักขระออกเป็นคอลัมน์ที่แตกต่างกัน
- B =รายการที่ว่างเปล่าใหม่
- สำหรับ col in A ทำ
- ถ้า col ถูกจัดเรียงแล้วให้ใส่ 0 ลงใน B
- มิฉะนั้นให้แทรก 1 ลงใน B
- คืนค่าผลรวมขององค์ประกอบทั้งหมดใน B
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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"]))
อินพุต
["cba","daf","ghi"]
ผลลัพธ์
1
