Ones and Zeros

发表于 | 分类于

给定一个由”0””1”组成的字符串列表(如{“0”, “110”, “1001”})。找出可以由m个0和n个1组成的最大字符串个数。

算法采用一个m+1行和n+1列的数组保存每次迭代后的对应numOfZero个0，numOfOne个1组成的个数加一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] matrix = new int[m + 1][n + 1];
        int numOfZero = 0;
        int numOfOne = 0;
        for (int i=0;i<strs.length;i++) {
            numOfZero = numOfOne = 0;
            String s = strs[i];
            for (int j=0;j<s.length();j++) {
                if (s.charAt(j) == '0') {
                    numOfZero++;
                } else {
                    numOfOne++;
                }
            }
            for (int x=m;x>=numOfZero;x--) {
                for (int y=n;y>=numOfOne;y--) {
                    matrix[x][y] = Math.max(matrix[x][y], matrix[x-numOfZero][y-numOfOne] + 1);
                }
            }
        }
        return matrix[m][n];
    }
}