LeetCode 955. Delete Columns to Make Sorted II

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"}));
	}
}