Top Down Java DP O(m*n*string length) still slow TLE


  • -1
    D

    class Key
    {
    int i,m,n;
    Key(int i, int m, int n)
    {
    this.i = i;
    this.m = m;
    this.n = n;
    }

    public boolean equals(Object o) {

        // If the object is compared with itself then return true  
        if (o == this) {
            return true;
        }
    
        if (!(o instanceof Key)) {
            return false;
        }
        Key k = (Key) o;
        return (m==k.m && n==k.n && i==k.i);
    }
    public int hashCode()
    {
        return new Integer(m*n*i).hashCode();
    }
    public String toString()
    {
        return i +"#" + m + "#" + n;
    }
    

    }

    public class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
    Map<Key,Integer> solution = new HashMap<Key,Integer>();
    int[][] cache = new int[strs.length][2];
    for(int i=0;i<cache.length;i++)
    {
    for(int j=0;j<strs[i].length();j++)
    if(strs[i].charAt(j) == '0')
    cache[i][0]++;
    else
    cache[i][1]++;
    }

        boolean[] parent = new boolean[strs.length];
        int ans = rec_impl(strs.length,strs,m,n,solution,parent,cache);
        return ans; 
    }
    
    public int rec_impl(int i, String[] strs, int m, int n, Map<Key,Integer> solution, boolean[] parent,int[][] cache) 
    {
       if(solution.containsKey(new Key(i,m,n)))
       {
           return solution.get(new Key(i,m,n));
       }
       if(m<0 || n<0)
            return 0;
       if(i == 1)
        {
            String first = strs[i-1];
            int num_0 = cache[i-1][0];
            int num_1 = cache[i-1][1];
            if(m >= num_0 && n >= num_1)
            {
                parent[i-1] = true;
                solution.put(new Key(i,m,n),1);
            }
            else
            {
                solution.put(new Key(i,m,n),0);
            }
            return solution.get(new Key(i,m,n));
        }
        String element = strs[i-1];
        int num_0 = cache[i-1][0];
        int num_1 = cache[i-1][1];
        int opt = rec_impl(i-1,strs,m,n,solution,parent,cache);
        solution.put(new Key(i,m,n),opt);
        if(m>=num_0 && n>=num_1)
        {
            int opt1 = rec_impl(i-1,strs,m-num_0,n-num_1,solution,parent,cache)+1;
            if(opt < opt1)
            {
                solution.put(new Key(i,m,n),opt1);
                parent[i-1] = true;
            }
        }
        return solution.get(new Key(i,m,n));
    }
    

    }


  • 0

    I was thinking the top-down way with cached results could actually avoid those unused calculations. Do you have any comments why this method got TLE?


  • 0
    D

    @zzg_zzm No Idea the same bottom up approach got accepted.


Log in to reply
 

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