Java 19ms beats 100% no DP but Greedy !


  • 1
    D

    This solution runs 19ms and beats 100% in Java submission with 63 test cases. But it is not in DP, so I am wonder whether it is correct if more corner test cases are added. Need help !!!

    public int findMaxForm(String[] strs, int m, int n) {
            Arrays.sort(strs, new Comparator<String>(){
                public int compare(String s1, String s2) {
                    int val = s1.length() - s2.length();
                    if(val != 0)
                        return val;
                    return s1.compareTo(s2);
                }
            });
            int result = 0;
            for(int i = 0; i < strs.length; i++)
                result = Math.max(result, dfs(strs, m, n, i));
            return result;
        }
        public int dfs(String[] strs, int m, int n, int start) {
            boolean flag;
            int result = 0, mm, nn;
            for(; start < strs.length; start++) {
                char[] c = strs[start].toCharArray();
                flag = true;
                if(c.length > m + n)
                    break;
                mm = m;
                nn = n;
                for(int i = 0; i < c.length; i++) {
                    if(c[i] == '0' && m > 0)
                        m--;
                    else if(c[i] == '1' && n > 0)
                        n--;
                    else {
                        flag = false;
                        break;
                    }
                }
                if(flag)
                    result++;
                else {
                    m = mm;
                    n = nn;
                }
            }
            return result;
        }
    

  • 0

    Very nice greedy solution!

    The reason that you're faster is because your solution is essentially greedy. While DP memorizes results, it is just memorized brutal force, greedy will definitely be faster.

    I modified your code to make the style better, and more understandable. While by making it recursion it will be slightly slower (beating 99.8%), but it increases the readability a lot.

    I'm not very good at recursion, thus this version still contains global variable, maybe someone can help me improve it :D

    public int findMaxForm(String[] strs, int m, int n) {
            Arrays.sort(strs, new Comparator<String>(){
                public int compare(String s1, String s2) {
                    int diff = s1.length() - s2.length();
                    if (diff != 0) return diff;
                    return s1.compareTo(s2);
                }
            });
            for (int i = 0; i < strs.length; i++) searchMax(strs, m, n, i, 0);
            return result;
        }
        int result = 0;
        public void searchMax(String[] strs, int m, int n, int index, int currentMax) {
            //can't match any more, return
            if (index >= strs.length || strs[index].length() > m + n) {
                result = Math.max(currentMax, result);
                return;
            }
            boolean canAdd = true;
            int result = 0, newM = m, newN = n;
    
            for(char c: strs[index].toCharArray()) {
                if(c == '0' && newM > 0) {
                    newM--;
                } else if (c == '1' && newN > 0) {
                    newN--;
                } else { //can't add this new result
                    canAdd = false;
                    break;
                }
            }
            if (canAdd) {
                searchMax(strs, newM, newN, index + 1, currentMax + 1);
            } else {
                searchMax(strs, m, n, index + 1, currentMax);
            }
        }
    

  • 0
    D

    @meowmeow
    Yes, this is greedy solution. So, I am not sure whether it will remain correct if more corner cases are added.
    As for your version, you can let recursion return int so as to avoid global variable.


  • 2
    B

    would fail this test case:

    ["0001","0101","1000","1000"]
    9
    3

    resulted 2 expected 3


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.