474. Ones and Zeroes

 一刷 06/2022

Version #1 DP - 2 Dimensions

一个bug就是因为没有使用3D的dp，所以如果iterate zeros and ones 的时候从smaller to larger，就会造成重复加的情况

因为dp是looking backwards

所以只有从大向小更新才能保证上一层的数据不被污染

Time O(len * MN)

Space O(MN)

Runtime: 28 ms, faster than 82.25% of Java online submissions for Ones and Zeroes.

Memory Usage: 42.6 MB, less than 64.69% of Java online submissions for Ones and Zeroes.

class Solution {

    public int findMaxForm(String[] strs, int m, int n) {

        // 600 * (100 + 100^2)= 6 * 10^6

        // dp[i][j] - The max number of strings that having less than i zeros and j ones

        int max = 0;

        int[][] dp = new int[m + 1][n + 1];

        for (String str : strs) {

            int[] counts = count(str);

            int zeros = counts[0];

            int ones = counts[1];

            if (zeros > m || ones > n) {

                continue;

            }

            for(int i = m; i >= zeros; i--) {

                for (int j = n; j >= ones; j--) {

                    dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);

                }

            }

        }

        return dp[m][n];

    }

    

    // count the number of zeros and ones in given string

    private int[] count(String str) {

        int zeros = 0;

        int ones = 0;

        for (int i = 0; i < str.length(); i++) {

            if (str.charAt(i) == '0') {

                zeros++;

            } else {

                ones++;

            }

        }

        return new int[]{zeros, ones};

    }

}