Java DP solution with explanation


  • 8
    E

    The idea is to build up the solution for 0..m zeros and 0..n ones, from only knowing 1 string, 2 strings, ..., up to n strings.

    For example, for array = {"10", "0", "1"}, m = 1, n = 1.

    • for first string "10":
      • zero = 0, one = 0
      • zero = 1, one = 0
      • zero = 0, one = 1
      • zero = 1, one = 1, can form "10" [+1]
    • continue on the second string "0", with previous knowledge of string "10":
      • zero = 0, one = 0
      • zero = 1, one = 0, can form "0" [+1]
      • zero = 0, one = 1
      • zero = 1, one = 1, can form "0" [+1] or 1 string ("10"), known from previous string
    • continue on the last string "1", with previous knowledge of strings "10" and "0":
      • zero = 0, one = 0
      • zero = 1, one = 0, can't form "1", but we know it can form 1 string ("0") from previous set of strings
      • zero = 0, one = 1, can form "1" (+1)
      • zero = 1, one = 1, (can form "1" and 1 more string ("0") with zero = 1, one = 0, known from previous set of strings) or (1 string ("10"), known from previous set of strings)

    Hence, at the end, we know that with zero = 1, one = 1, with string "10", "0", and "1", the maximum number of strings we can form is 2.

    public int findMaxForm(String[] strs, int m, int n) {
        int[][] max = new int[m + 1][n + 1];
        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            
            int neededZero = 0;
            int neededOne = 0;
            for (int j = 0; j < str.length(); j++) {
                if (str.charAt(j) == '0') {
                    neededZero++;
                } else {
                    neededOne++;
                }
            }
            
            int[][] newMax = new int[m + 1][n + 1];
            
            for (int zero = 0; zero <= m; zero++) {
                for (int one = 0; one <= n; one++) {
                    if (zero >= neededZero && one >= neededOne) {
                        int zeroLeft = zero - neededZero;
                        int oneLeft = one - neededOne;
                        newMax[zero][one] = Math.max(1 + max[zeroLeft][oneLeft], max[zero][one]);
                    } else {
                        newMax[zero][one] = max[zero][one];
                    }
                }
            }
            
            max = newMax;
        }
        return max[m][n];
    }
    

  • 0
    C

    can you give your explanation?


  • 0
    E

    @cainiaofei I've added some description to my approach above. Hope it's helpful.


Log in to reply
 

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