474. Ones and Zeroes (Solution 2)

/**
474. Ones and Zeroes
https://leetcode.com/problems/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. 1 <= strs.length <= 600
2. 1 <= strs[i].length <= 100
3. strs[i] consists only of digits '0' and '1'.
4. 1 <= m, n <= 100
*/

pub struct Solution {}

impl Solution {
    /*
    Solution 2: Recursive + Memorization, Time:O(m*n*length), Space:O(m*n*length);
    */
    pub fn find_max_form(strs: Vec<String>, m: i32, n: i32) -> i32 {
        //memo help to save index,m,n
        let M = (m as usize) + 1;
        let N = (n as usize) + 1;
        //M rows * N cols, size of length
        let mut memo = vec![vec![vec![-1; N]; M]; strs.len()];
        Self::help(0, m, n, &strs, memo.as_mut())
        //3D array example: two 3 rows * 4 cols arrays
        //let mut memo = vec![vec![vec![0;4];3];2];
    }

    pub fn help(index: i32, m: i32, n: i32, strs: &Vec<String>, memo: &mut Vec<Vec<Vec<i32>>>) -> i32 {
        let length: i32 = strs.len() as i32;
        if index == length {
            return 0;
        }
        let currentValue = memo[index as usize][m as usize][n as usize];
        if (currentValue != -1) {
            return currentValue;
        }
        let mut currentString: String = String::from(&strs[index as usize]);
        let mut zeroCount = Self::countZero(&currentString);
        let mut oneCount = currentString.len() as i32 - zeroCount;
        //m for 0, n for 1
        let mut calculateCurStr = 0;
        if m >= zeroCount && n >= oneCount {
            calculateCurStr = 1 + Self::help(index + 1, m - zeroCount, n - oneCount, &strs, memo);
        }
        let mut calculateOtherStr = Self::help(index + 1, m, n, &strs, memo);
        let res = std::cmp::max(calculateCurStr, calculateOtherStr);
        memo[index as usize][m as usize][n as usize] = res;
        res
    }

    fn countZero(str: &String) -> i32 {
        let mut result = 0;
        for c in str.chars() {
            if (c == '0') {
                result = result + 1;
            }
        }
        result
    }
}