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.


  • 0

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

    was my point.

    Hey! Can you please explain the runtime and space complexity of this solution?


Log in to reply
 

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