刪列造序 II【中等】
給定由 N 個(gè)小寫字母字符串組成的數(shù)組 A，其中每個(gè)字符串長(zhǎng)度相等颤陶。
選取一個(gè)刪除索引序列颗管，對(duì)于 A 中的每個(gè)字符串，刪除對(duì)應(yīng)每個(gè)索引處的字符指郁。
比如忙上，有 A = ["abcdef", "uvwxyz"]，刪除索引序列 {0, 2, 3}闲坎，刪除后 A 為["bef", "vyz"]。
假設(shè)茬斧，我們選擇了一組刪除索引 D腰懂，那么在執(zhí)行刪除操作之后，最終得到的數(shù)組的元素是按 字典序（A[0] <= A[1] <= A[2] ... <= A[A.length - 1]）排列的项秉，然后請(qǐng)你返回 D.length 的最小可能值绣溜。
示例 1：
輸入：["ca","bb","ac"]
輸出：1
解釋：
刪除第一列后，A = ["a", "b", "c"]娄蔼。
現(xiàn)在 A 中元素是按字典排列的 (即怖喻，A[0] <= A[1] <= A[2])。
我們至少需要進(jìn)行 1 次刪除岁诉，因?yàn)樽畛?A 不是按字典序排列的锚沸，所以答案是 1。
示例 2：
輸入：["xc","yb","za"]
輸出：0
解釋：
A 的列已經(jīng)是按字典序排列了涕癣，所以我們不需要?jiǎng)h除任何東西哗蜈。
注意 A 的行不需要按字典序排列。
也就是說(shuō)坠韩，A[0][0] <= A[0][1] <= ... 不一定成立距潘。
示例 3：
輸入：["zyx","wvu","tsr"]
輸出：3
解釋：
我們必須刪掉每一列。
提示：
1 <= A.length <= 1001 <= A[i].length <= 100
解題思路
作者有點(diǎn)笨只搁，做了好久這道題還是沒(méi)通過(guò)音比，于是就參考了大佬們的解答，下面就大佬的代碼說(shuō)一下這道題的解題思路吧氢惋。首先思考什么樣的序列才是字典序洞翩，所謂字典序就是像查字典一樣。假如我們想查hui這個(gè)音明肮，先要找到y(tǒng)字母的那部分菱农，然后會(huì)看見(jiàn)很多以y開頭的拼音，就要進(jìn)行篩選找出yu柿估，進(jìn)而找出yui循未。在這里一樣，字典序就是像['xy','yy','za']，['xa','xc','yb']這類的的妖。于是做這道題就要思考以下幾種情況：
1.看是否有序绣檬，如果無(wú)序，直接刪除嫂粟。
例：[
'xcz',
'zdv',
'yfa'
]
上面第一列分別是x娇未、z、y,并不是有序的星虹，于是放棄這一列進(jìn)行下一列的判斷零抬。
2.如果有序，看是否有相等元素宽涌，如果沒(méi)有平夜，直接返回結(jié)果。
例：[
'xcz',
'zdv',
'yfa'
]
第一列按照情況1處理卸亮，直接刪除忽妒。然后判斷第二列，第二列有序并且不含相等元素兼贸，所以直接返回結(jié)果為1段直。
3.如果有相等元素，得到相等元素的下標(biāo)溶诞，然后對(duì)后面的列只判斷有相等元素的幾行鸯檬。
例：[
'xcz',
'zcv',
'yfa'
]
假如第二列變成了c、c很澄、f京闰，含有相等元素，就需要進(jìn)行第三列的判斷甩苛，
對(duì)第三列的判斷也是按照情況1蹂楣、2、3依次判斷的讯蒲，直到滿足條件返回結(jié)果痊土。
按照上面的情況分析之后，思路就已經(jīng)很清楚了墨林，就是取出所有列赁酝，依次對(duì)情況1,2,3進(jìn)行判斷，最后返回相應(yīng)的結(jié)果值旭等。下面是leetcode上的代碼：
class Solution:
def minDeletionSize(self, A):
"""
:type A: List[str]
:rtype: int
"""
def isright(i,l):#第i列是否按照嚴(yán)格字典序（不含相等）酌呆，這里只比較l中出現(xiàn)的行數(shù)
for j in l:
if A[j][i] > A[j+1][i]:
return 1
return 0
def isequal(i,l):#第i列是否有的情況，這里只比較l中出現(xiàn)的行數(shù)搔耕，有的話返回1和相等的行標(biāo)號(hào)
flag = 0
child = []
for j in l:
if A[j][i] == A[j+1][i]:
child.append(j)
flag = 1
return flag,child
res = 0;
child = range(len(A)-1)
for i in range(len(A[0])):
h = isright(i,child)
if h == 0:
eq,child1 = isequal(i,child)
if eq == 0:
return res
elif eq == 1:
child = child1
res += h
return res
