LeetCode 解題紀錄 955. Delete Columns to Make Sorted II

Delete Columns to Make Sorted II - LeetCode

題目

給定一個長度為 n 的字串陣列 strs，陣列中的字串長度皆相同，你可以一次刪除所有字串中的第 i 個位置字元，要求返回刪除最少的位置後能讓字串的排序 strs[0] < strs[1] < .. < strs[n-1]

條件

• 1 ≤ n ≤ 100
• 1 ≤ strs[i] ≤ 100

觀察

• 先針對strs[0] 與 strs[1] 檢查排序，如果是已排序則可以接著檢查 strs[1] 與 strs[2]
• 當比對 strs[i] strs[i+1] 時，我們可以一個個字元檢查，當發現不合法情形時，將該索引加入 Set，同時因為這會影響之的已排序結果，要退回第一個重頭開始檢查
• 已經刪除的索引要跳過不須比對該位置字元

解法(Compare + Set)

• 使用一個 set 用來儲存已刪除的位置
• 比對時如果該索引存在則跳過
• 當發現不合法的字元時，需要重新比對

class Solution {
    public int minDeletionSize(String[] strs) {
        Set<Integer> deleted = new HashSet();
        int n = strs.length, m = strs[0].length();
        for(int i=1;i<n;i++) {
            String s0 = strs[i-1];
            String s1 = strs[i];            
            for(int j=0;j<m;j++) {
                // 跳過已刪除索引
                if(!deleted.contains(j)) {
                    if(s0.charAt(j) != s1.charAt(j)) {
                        // 如果是不合法，加入該索引並重新開始
                        if(s0.charAt(j) > s1.charAt(j)) {
                            deleted.add(j);
                            i=0;
                        }
                        // 只要不等於就可以停止比對
                        break;
                    }
                }
            }            
        }
        return deleted.size();        
    }
}

結果

TC：O(m²*n) n 是 strs的長度，m 是 strs[i] 的長度

SC：O(m)