C++ How to figure out it's greedy!
To find out the minimum operation, I considered BFS, dp or greedy. It\'s not straight forward for me to decide to use which one. First, I listed some ground tru
To find out the minimum operation, I considered BFS, dp or greedy. It\'s not straight forward for me to decide to use which one. First, I listed some ground truth:\n\n- For each string, if we make sure it\'s greater than its previous string, then this entire string list is sorted.\n- For string A and string B(B is the next string atfer A). If the i-th character of string A is already greater than string B, we don\'t need to consider the following characters. If the i-th character of string A equals i-th character of string B, we consider the following characters. We need to save this information.\n- We start from column 0, if column 0 satisfy the constraint, we don\'t need to consider the case delete column 0.\n\nWith the above ground truth, we know greedy is the right answer. We use a vector to save the order information of string A and its following string B.\nmark[i] = 0: after necessary delete, string i equals string i-1.\nmark[i] = 1: after necessary delete, string i greater than string i-1.\nThen we update mark vector each time.\n```\nclass Solution {\npublic:\n    int minDeletionSize(vector<string>& A) {\n        int len = A.size();\n        if (len < 2) {\n            return 0;\n        }\n        int count = 0;\n        int range = A[0].length();\n        vector<int> mark(len, 0);\n        for(int i = 0; i < range; i++){\n            if (!check(i, len, A, mark)) {\n                count++;\n            } else {\n                updateMark(i, len, A, mark);\n            }\n        }\n        return count;\n    }\nprivate:\n    bool check(int pos, int len, vector<string> A, vector<int> mark){\n        for(int i = 1; i < len; i++){\n            if (mark[i]==0 && A[i][pos]<A[i-1][pos]) {\n                return false;\n            }\n        }\n        return true;\n    }\n    void updateMark(int pos, int len, vector<string> A, vector<int>& mark){\n        for(int i = 1; i < len; i++){\n            if (mark[i]==0 && A[i][pos]>A[i-1][pos]) {\n                mark[i] = 1;\n            }\n        }\n        return ;\n    }\n};\n```
[]