-
Notifications
You must be signed in to change notification settings - Fork 0
/
Solution.java
41 lines (33 loc) · 1.01 KB
/
Solution.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//
// DP, Array, String(Ones and Zeroes)
// https://leetcode.com/problems/ones-and-zeroes/
// Created by hyungwook on 2022/06/08.
//
public class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= strs.length; i++) {
int[] counts = getCounts(strs[i - 1]);
int zeroCount = counts[0];
int oneCount = counts[1];
for (int j = m; j >= zeroCount; j--) {
for (int k = n; k >= oneCount; k--) {
dp[j][k] = Math.max(dp[j][k], dp[j - zeroCount][k - oneCount] + 1);
}
}
}
return dp[m][n];
}
private int[] getCounts(String str) {
int zeroCount = 0;
int oneCount = 0;
for (char c : str.toCharArray()) {
if (c == '0') {
zeroCount++;
} else {
oneCount++;
}
}
return new int[]{zeroCount, oneCount};
}
}