這是悅樂(lè)書(shū)的第362次更新，第389篇原創(chuàng)

01 看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級(jí)別的第224題（順位題號(hào)是944）。我們給出了一個(gè)N個(gè)小寫(xiě)字母串的數(shù)組A，它們的長(zhǎng)度都相同。

現(xiàn)在，我們可以選擇任何一組刪除索引，對(duì)于每個(gè)字符串，我們刪除這些索引中的所有字符。

例如，如果我們有一個(gè)數(shù)組A = [“abcdef”，“uvwxyz”]和刪除索引{0,2,3}，那么刪除后的數(shù)組變成了[“bef”，“vyz”]，縱向上看，每一列是[“b”，“v”]，[“e”，“y”]和[“f”，“z”]。（形式上，第c列是[A[0][c]，A[1][c]，...，A[A.length-1][c]]。）

假設(shè)我們選擇了一組刪除索引D，使得在刪除之后，A中的每個(gè)剩余列都處于遞增排序順序。返回D.length的最小可能值。例如：

輸入：[“cba”，“daf”，“ghi”]
輸出：1
說(shuō)明：在選擇D = {1}之后，每列[“c”，“d”，“g”]和[“a”，“f”，“i”]處于遞增的排序順序。如果我們選擇D = {}，則列[“b”，“a”，“h”]將不是遞增排序順序。

輸入：[“a”，“b”]
輸出：0
說(shuō)明：D = {}

輸入：[“zyx”，“wvu”，“tsr”]
輸出：3
說(shuō)明：D = {0,1,2}

注意：

• 1 <= A.length <= 100

• 1 <= A[i].length <= 1000
  
  

02 第一種解法

題目的意思是A中包含了許多長(zhǎng)度一樣的字符串元素，從縱向來(lái)看，單個(gè)字符串中的每一列字符大小關(guān)系需要是遞增的，如果不是，則需要?jiǎng)h除，問(wèn)需要?jiǎng)h除多少列字符，才能保證所有列的字符大小關(guān)系都是遞增的。結(jié)合給的示例來(lái)看，[“cba”，“daf”，“ghi”]，縱向來(lái)看就變成了下面這樣：

cba -->  c b a
daf -->  d a f
ghi -->  g h i

第一列為cdg，是遞增的，不用刪除，第二列為bah，不是遞增，需要?jiǎng)h除，第三列是afi，是遞增的，不用刪除，所以最后需要?jiǎng)h除中間那列的字符，就能保證所有列的字符大小關(guān)系都是遞增的，所以返回1。

思路：根據(jù)上面我們的分析，直接上兩層循環(huán)就行，外層控制列數(shù)，內(nèi)層控制行數(shù)，注意下標(biāo)不能越界。

此解法的時(shí)間復(fù)雜度為O(A)，A為數(shù)組A中所有字符的個(gè)數(shù)，空間復(fù)雜度為O(1)。

public int minDeletionSize(String[] A) {
    int n = A[0].length(), len = A.length;
    int count = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<len-1; j++) {
            if (A[j].charAt(i) > A[j+1].charAt(i)) {
                count++;
                break;
            }
        }
    }
    return count;
}

03 第二種解法

我們還可以使用二維數(shù)組來(lái)解題。

在第一種解法中，通過(guò)縱向觀察，可以將A中的所有字符看成是一個(gè)二維數(shù)組，行是A中元素個(gè)數(shù)，列是A中單個(gè)字符串的長(zhǎng)度，先將字符初始化進(jìn)二維數(shù)組中，然后遍歷二維數(shù)組，比較列上前后字符的大小關(guān)系，需要?jiǎng)h除（前后不是遞增順序）就計(jì)數(shù)加1，最后返回累加的count。

此解法的時(shí)間復(fù)雜度時(shí)O(A)，A為數(shù)組A中所有字符的個(gè)數(shù)，空間復(fù)雜度為O(N*M)，N為數(shù)組A的長(zhǎng)度，M為A中單個(gè)元素的長(zhǎng)度。

public int minDeletionSize2(String[] A) {
    int row = A.length, col = A[0].length();
    char[][] arr = new char[row][col];
    for (int i=0; i<A.length; i++) {
        arr[i] = A[i].toCharArray();
    }
    int count = 0;
    for (int i=0; i<col; i++) {
        for (int j=0; j<row-1; j++) {
            if (arr[j][i] > arr[j+1][i]) {
                count++;
                break;
            }
        }
    }
    return count;
}

04 小結(jié)

算法專題目前已連續(xù)日更超過(guò)七個(gè)月，算法題文章230+篇，公眾號(hào)對(duì)話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集。

以上就是全部?jī)?nèi)容，如果大家有什么好的解法思路、建議或者其他問(wèn)題，可以下方留言交流，點(diǎn)贊、留言、轉(zhuǎn)發(fā)就是對(duì)我最大的回報(bào)和支持！