JAVA dp Time O(N^3), Beat 100%. First 100% on LeetCode .Cool~


  • 0
    Y
    public class Solution {
        String op="";
        ArrayList<Integer> ar=new ArrayList();
        ArrayList<Integer>[][] dp;
        ArrayList<Integer> dfs(int s,int t)
        {
            if(dp[s][t].size()>0) return dp[s][t];
            ArrayList<Integer> ans=new ArrayList<>();
            if(s==t)
            {
                ans.add(ar.get(s));
                dp[s][t]=ans;
                return ans;
            }
            for(int k=s;k<t;k++)
            {
                ArrayList<Integer> left=dfs(s,k);
                ArrayList<Integer> right=dfs(k+1,t);
                for(int i=0;i<left.size();i++)
                for(int j=0;j<right.size();j++)
                {
                    int a=left.get(i);
                    int b=right.get(j);
                    ans.add(op.charAt(k)=='+'?a+b:(op.charAt(k)=='-'?a-b:a*b));
                }
            }
            dp[s][t]=ans;
            return ans;
        }
        public List<Integer> diffWaysToCompute(String input) {
             int v=-1;
             
             for(int i=0;i<input.length();i++)
             {
                 if(Character.isDigit(input.charAt(i)))
                 {
                     if(v==-1) v=0;
                     v=v*10+(int)input.charAt(i)-(int)'0';
                 }else
                 {
                     op+=input.charAt(i);
                     ar.add(v);v=-1;
                 }
             }
             
             if(v!=-1)
             ar.add(v);
             int n=ar.size();
             dp=new ArrayList[n][n];
             for(int i=0;i<n;i++)
             for(int j=0;j<n;j++) dp[i][j]=new ArrayList<Integer>();
             return dfs(0,ar.size()-1);
        }
    }
    

  • 0
    D

    Before you declare your solution O(N^3), can you check it carefully?

    There are O(N^2) subproblems, you scan through each subproblem (O(n)) searching for operators and do recursive calls. So it make O(N^3) up to this point. What about combining the results? It is O(1) in your opinion?

    Try running your "O(N^3)" program on "2*3-4*5-2*3-4*5*2*3-4*5-2*3-4*5+2*3-4*5-2*3-4*5*2*3-4*5-2*3-4*5*5*2*3-4*5-2*3-4*5" and see if it ever returns.


  • 0

    Sorry, could you explain a little about your code. Looks kind of complex to me.


  • 0

    @damluar said in JAVA dp Time O(N^3), Beat 100%. First 100% on LeetCode .Cool~:

    Try running your "O(N^3)" program on "2*3-4*5-2*3-4*5*2*3-4*5-2*3-4*5+2*3-4*5-2*3-4*5*2*3-4*5-2*3-4*5*5*2*3-4*5-2*3-4*5" and see if it ever returns.

    even the OJ can't finish within time limit. What about you come up a better one to defeat OJ?


  • 0
    D

    @taylorzhangyx It cannot finish because the running time is much much bigger than N^3. That was my point.


Log in to reply
 

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