C++ DFS solution (13ms) beats 99.41%


  • 0
    W

    my C++ DFS solution: (13 ms)

    1. Sort the string (by length) to decrease the runtime because basically the shorter the string is, the more likely it will be selected.
    2. Use DFS to go through all the possible combination and find the longest one

    Although I come up with this idea, I still confuse about why it's faster than DP solution and what the Time Complexity it is. I will appreciate it if someone can tell me.

    class Solution {
    public:
        struct Cmp {
            bool operator()(string& s1, string& s2) {
                return s1.length() != s2.length() ? s1.length() < s2.length() : s1 < s2;
            }
        };
        
        int findMaxForm(vector<string>& strs, int m, int n) {
            sort(strs.begin(), strs.end(), Cmp());
            vector<int> numOfZero;
            for(string s : strs) {
                numOfZero.push_back(count(s.begin(), s.end(), '0'));
            }
            int maxLen = 0;
            dfs(strs, numOfZero, m, n, 0, 0, maxLen);
            return maxLen;
        }
        
        void dfs(vector<string>& strs, vector<int>& numOfZero, int m, int n, int k, int formLen, int& maxLen) {
            if(maxLen >= formLen + strs.size() - k) {
                return;
            }
            maxLen = max(maxLen, formLen);
            for(int i = k; i < strs.size(); i++) {
                if(i == k || strs[i] != strs[i-1]) {
                    int zeros = numOfZero[i], ones = strs[i].length() - zeros;
                    if(m - zeros >= 0 && n - ones >= 0) {
                        dfs(strs, numOfZero, m - zeros, n - ones, i + 1, formLen + 1, maxLen);
                    }
                }
            }
        }
    };
    

  • 0

    @wszk1992
    I think the reason this solution is faster than the DP one is, that the solution sort the strings by string length and by string value.

    • In most of the test cases, m is larger than n. If you change the comparator from return s1.length() != s2.length() ? s1.length() < s2.length() : s1 < s2; to return s1.length() != s2.length() ? s1.length() < s2.length() : s1 > s2;, the solution will be slower than the DP one.

    • If you remove the sorting completely, you will get TLE.

    Hope this helps.


  • 0
    S

    public class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
    int len = strs.length;
    List<int[]> freqs = new LinkedList<int[]>();

        Arrays.sort(strs,(s1,s2) ->s2.length()-s1.length());
        for(int i=0;i<len;i++){
           int[] freq = new int[2];
            String str = strs[i];
            int slen = str.length();
            for(int j=0;j<slen;j++){
                freq[str.charAt(j)-'0']++;
               
            }
            freqs.add(freq);
        }
       return helper(freqs,0,m,n);
       
    }
    
    
    public int helper(List<int[]> cand, int pos,int m,int n ){
        int len = cand.size();
        int dep = Integer.MIN_VALUE;
        if(pos>=len) return 0;
        for(int i = pos;i<len;i++){
            int[] temp = cand.get(i);
            m-= temp[0];
            n-= temp[1];
            if(m>=0&&n>=0){
                dep =Math.max(dep,helper(cand,i+1,m,n)+1);
            }
            m+= temp[0];
            n+= temp[1];
        }
       return dep==Integer.MIN_VALUE?0 : dep;
    }
    

    }

    hello,I also used DFS,pass 13 test cases. When the input is ["11","11","0","0","10","1","1","0","11","1","0","111","11111000","0","11","000","1","1","0","00","1","101","001","000","0","00","0011","0","10000"]
    90
    66
    I got TLE,do you have any suggestions? I also sorted the string.Thanks.


Log in to reply
 

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