474. Ones and Zeroes

Link

Solution

Define : dp Array for this problem

dp[i][m][n]: the maximun count i : from strings[0] ~ string[i] m : how many 0s we can offer n : how many 1s we can offer

T: O(kmn + kl), k means the lenght of strs, l means the average of str length kmn : for calcaulation the dp in loop kl : for calcatation the 0, 1 count of each string

   public int findMaxForm(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length][m+1][n+1]; 
        // dp[i][j][k], i : from 0 to i in strs, j : remained 0 count, k : remained 1 counts        
        for(int i = 0; i < strs.length; i++){
            int[] count = getCount(strs[i]); 
            for(int j = 0; j <= m; j++){
                for(int k = 0; k <= n; k++){
                    if(i == 0){
                        dp[i][j][k] = (j >= count[0] && k >= count[1]) ? 1 : 0;
                    }
                    else if(j >= count[0] && k >= count[1]){
                       dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-count[0]][k-count[1]]+1);
                    }
                    else{
                        // System.out.println(dp[i-1][j][k] +  ":" + (1 + dp[i-1][j-count[0]][k-count[1]]));
                       dp[i][j][k] =  dp[i-1][j][k];
                    }
                }   
            }
        }
        return dp[strs.length-1][m][n];
    }
   
    
    
    public int[] getCount(String s){
        int[] ret = new int[2];
        for(char c : s.toCharArray()){
            if(c == '0'){
                ret[0]++;
            }
            else{
                ret[1]++;
            }
        }
        return ret;
    }