Yet another Java DP solution (18ms, beats 100%)


  • 0
    J

    Time complexity: O(LN + Llg(L)) (L as strs.length)
    Space complexity: O(L+N)
    Currently beats 100%

    public class Solution {
        private class Count implements Comparable<Count>{
            int zero;
            int one;
            Count(String str) {
                zero = 0;
                one = 0;
                for (int i = 0; i < str.length(); i++) {
                    if (str.charAt(i) == '1') one++;
                    else zero++;
                }
            }
            public int compareTo(Count b) {
                return this.zero - b.zero;
            }
        }
        public int findMaxForm(String[] strs, int m, int n) {
            Count[] strings = new Count[strs.length];
            for (int i = 0; i < strs.length; i++) {
                strings[i] = new Count(strs[i]);
            }
            Arrays.sort(strings);
            int dp[][][] = new int[2][n + 1][2];
            int curI = 0;
            for (int i = 1; i <= strings.length; i++) {
                Count cur = strings[i - 1];
                int prevI = curI;
                curI ^= 1;
                for (int j = 0; j <= n; j++) {
                    if (j - cur.one >= 0 && (j == 0 ? 0 : dp[prevI][j - 1][1]) + cur.zero <= m && dp[prevI][j - cur.one][0] + 1 > dp[prevI][j][0]) {
                        dp[curI][j][0] = dp[prevI][j - cur.one][0] + 1;
                        dp[curI][j][1] = dp[prevI][j - cur.one][1] + cur.zero;
                    } else {
                        dp[curI][j][0] = dp[prevI][j][0];
                        dp[curI][j][1] = dp[prevI][j][1];
                    }
                }
            }
            return dp[strings.length & 1][n][0];
        }
    }
    

Log in to reply
 

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