955. Delete Columns to Make Sorted II Medium

You are given an array of n strings strs, all of the same length.

We may choose any deletion indices, and we delete all the characters in those indices for each string.

完整介紹 https://leetcode.com/problems/delete-columns-to-make-sorted-ii/

這題有點難的是要看懂題目，要刪到讓所有的詞都依詞典順序的排列
做法如下

由左往右，每一列再由上往下，把自己和下一行的字母拿來比，會有三種可能性

1. 自己比下一列的字母大，直接出局，這行要砍掉，answer +1
2. 自己比下一列的字母小，通過 (且後面的字母也不用再比了，見下面說明)
3. 自己跟下一列的字母相同，註記下來 Repeat

當 Repeat 都沒有的時候，程式結束，回傳 answer (砍掉幾行)

範例題目

有重覆的字母以 R (Repeat)代表

執行完第一列，會 mark 出兩個地方有重覆的字母

後續執行沒必要再檢查的字母以 「-」表示
執行完第二列，index 2 的 R 會被移除，目標把 R 移光就搞定收工了

執行第三列會發現這列必須刪除，所以 answer + 1

執行完第四列後，將 R 全數移光，程式即結束，得到 answer 是 1

程式碼

public class A0955_DeleteColumnsToMakeSortedII {
	
    public int minDeletionSize(String[] strs) {
    	int ans = 0;
    	int[] sameNote = new int[strs.length]; // x 軸的長度 (上到下)
    	// x 軸往右走
    	for (int x=0; x<strs[0].length(); x++) {
    		
    		int[] tmpSameNote = sameNote.clone();
    		boolean isAllLess = true;
    		boolean isDelete = false;
    		// y 軸往下走，最後一行不用，所以 -1
    		for (int y=0; y<strs.length-1; y++) {
    			if (sameNote[y] == -1)
    				continue;
    			
    			char c1 = strs[y].charAt(x);
    			char c2 = strs[y+1].charAt(x);
    			if (c1 > c2) {
    				ans++;
    				isDelete = true;
    				break;
    			}
    			else if (c1 == c2) {
    				isAllLess = false;
    			}
    			else {
    				tmpSameNote[y] = -1;    				
    			}
    		}
    		if (! isDelete) {
    			sameNote = tmpSameNote;
    			if (isAllLess)
        			break;
    		}
    	}
    	return ans;
    }
}

unit test code

public class A0955_DeleteColumnsToMakeSortedIITest {
	@Test
	public void testMinDelete() {
		A0955_DeleteColumnsToMakeSortedII obj = new A0955_DeleteColumnsToMakeSortedII();

		assertEquals(1, obj.minDeletionSize(new String[] {"ca","bb","ac"}));
		assertEquals(0, obj.minDeletionSize(new String[] {"xc","yb","za"}));
		assertEquals(1, obj.minDeletionSize(new String[] {"xga","xfb","yfa"}));
		assertEquals(3, obj.minDeletionSize(new String[] {"zyx","wvu","tsr"}));
		assertEquals(1, obj.minDeletionSize(new String[] {"azzzhs","bayygo","ccxxfn", "cdooem", "eznndl", "fzmmck", "fzaxbj", "gzzaai"}));
	}
}