Java DFS+Cache, transfer to DP O(mn) space


  • 0

    DFS + Cache:

    public class Solution {
        int[][][] cache;
        public int findMaxForm(String[] strs, int m, int n) {
            cache = new int[strs.length][m + 1][n + 1];
            return search(0, m, n, strs);
        }
        private int search(int pos, int m, int n, String[] strs) {
            if (m < 0 || n < 0) return -1;
            if (pos > strs.length - 1) return 0;
            if (cache[pos][m][n] != 0) return cache[pos][m][n] == -1 ? 0 : cache[pos][m][n];
    
            int x = 0, y = 0;
            for (int i = 0; i < strs[pos].length(); i++) {
                if (strs[pos].charAt(i) == '0') x++;
                else y++;
            }
            int ret = Math.max(search(pos + 1, m - x, n - y, strs) + 1, search(pos + 1, m, n, strs));
            if (ret == 0) cache[pos][m][n] = -1;
            else cache[pos][m][n] = ret;
            return ret;
        }
    }
    

    DP:

    public class Solution {
        public int findMaxForm(String[] strs, int m, int n) {
            int[][][] F = new int[2][m + 1][n + 1];
    
            for (int pos = strs.length - 1; pos >= 0; pos--) {
                int x = 0, y = 0;
                for (int i = 0; i < strs[pos].length(); i++) {
                    if (strs[pos].charAt(i) == '0') x++;
                    else y++;
                }
    
                for (int i = 0; i <= m; i++) {
                    for (int j = 0; j <= n; j++) {
                        if (i - x < 0 || j - y < 0) {
                            F[pos % 2][i][j] = F[(pos + 1) % 2][i][j];
                        } else {
                            F[pos % 2][i][j] = Math.max(F[(pos + 1) % 2][i - x][j - y] + 1, F[(pos + 1) % 2][i][j]);
                        }
                    }
                }
            }
            return F[0][m][n];
        }
    }
    

  • 0
    I

    Did this get AC?


  • 0

Log in to reply
 

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