Time : O(strs.length * m * n); memory: O(m * n). Bottom-up DP


  • 0
    A

    Recursive solution with memorization with states (i, m, n) gots memory limit. The below solution is iterativa bottom-up solution. The states are d(position, zeroes, ones). The d[i][j][k] is the maximum answer which we can take for position i by using j zeroes and k ones.
    Time complexity: O(strs.length * m * n)
    memory complexity: O(m * n)

    public class Solution {
        
        public int findMaxForm(String[] strs, int m, int n) {
            int d[][][] = new int[2][m+1][n+1];
            
            int zeroes = getNumberOfZeroes(strs[0]);
            int ones = strs[0].length()-zeroes;
            
            for(int i = zeroes; i<=m; i++){
                for(int j = ones; j<=n; j++){
                    d[0][i][j] = 1;
                }
            }
            
            for (int i=1; i<strs.length; i++) {
                zeroes = getNumberOfZeroes(strs[i]);
                ones = strs[i].length()-zeroes;
                
                for (int j=0; j<=m; j++) {
                    for (int k=0; k<=n; k++) {
                        d[1][j][k] = d[0][j][k];
                        if (j-zeroes>=0 && k-ones>=0) {
                            d[1][j][k] = Math.max(d[0][j-zeroes][k-ones] + 1, d[0][j][k]);
                        }
                    }
                }
                
                copyCurToPrevState(d, m, n);
            }
            
            return d[0][m][n];
        }
        
        private void copyCurToPrevState(int d[][][], int m, int n) {
            for (int j=0; j<=m; j++) {
                for (int k=0; k<=n; k++) {
                    d[0][j][k] = d[1][j][k];
                }
            }
        }
        
        private int getNumberOfZeroes (String s) {
            int counter = 0;
            for (int i=0; i<s.length(); i++) {
                if (s.charAt(i)=='0') counter++;
            }
            return counter;
        }
    }
    

Log in to reply
 

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