source: https://leetcode.com/problems/ones-and-zeroes/description/
Ones and Zeroes
You are given an array of binary strings strs and two integers m and n.
Return the size of the largest subset of strs such that there are at most m 0’s and n 1’s in the subset.
A set x is a subset of a set y if all elements of x are also elements of y.
Example 1:
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0’s and 3 1’s is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1’s, greater than the maximum of 3.
Example 2:
Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.
Constraints:
- 1 <= strs.length <= 600
- 1 <= strs[i].length <= 100
- strs[i] consists only of digits ‘0’ and ‘1’.
- 1 <= m, n <= 100
|
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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
class Solution { public int findMaxForm(String[] strs, int m, int n) { Map<String, Pair> map = new HashMap<>(); int[][][] memo = new int[strs.length+1][m+1][n+1]; for(int[][] p:memo){ for(int[] q: p){ Arrays.fill(q, -1); } } for(String str: strs){ Pair p = getZandO(str); map.put(str, p); } return dfs(strs, m, n, map, 0, memo); } private int dfs(String[] strs, int m, int n, Map<String, Pair> map, int index, int[][][] memo){ if(index>=strs.length){ return 0; } if(memo[index][m][n]!=-1) return memo[index][m][n]; int max = Integer.MIN_VALUE; String s = strs[index]; Pair p = map.get(s); //for each str either we can add string in the subset, if it is valid if(isValid(p, m, n)){ max = Math.max(max, 1+dfs(strs, m-p.z, n-p.o, map, index+1, memo)); } //or we can skip it max = Math.max(max, dfs(strs, m, n, map, index+1, memo)); memo[index][m][n] = max; return max; } private boolean isValid(Pair p, int m, int n){ return p.z <= m && p.o <= n; } private Pair getZandO(String str){ char[] arr = str.toCharArray(); int z = 0; int o = 0; for(int i=0;i<arr.length;i++){ if(arr[i]=='1') o++; else z++; } return new Pair(z, o); } static class Pair{ private int z; private int o; public Pair(int z, int o){ this.z = z; this.o = o; } } } |