What's the time complexity for my recursive solution ??


  • 0

    I had hard time to analyze the time complexity for my solution, so anyone can help analyze what is the time complexity for non-DP and DP solutions (below is with DP support, can be easily modified to remove DP support) ??

    public class Solution {
        Map<String,List<Integer>> map = new HashMap<>();
        public List<Integer> diffWaysToCompute(String input) {
            List<Integer> res = new ArrayList<>();
            if(input.isEmpty())
                return res;
            if(map.containsKey(input))
                return map.get(input);
            boolean isPureNum = true;
            for(int i=0; i<input.length(); i++) {
                if(input.charAt(i)=='+' || input.charAt(i)=='-' || input.charAt(i)=='*') {
                    isPureNum = false;
                    List<Integer> prefixes = diffWaysToCompute(input.substring(0,i));
                    for(int prefix : prefixes) {
                        List<Integer> postfixes = diffWaysToCompute(input.substring(i+1));
                        for(int postfix : postfixes) {
                            if(input.charAt(i)=='+')
                                res.add(prefix+postfix);
                            else if(input.charAt(i)=='-')
                                res.add(prefix-postfix);
                            else 
                                res.add(prefix*postfix);
                        }
                    }
                }
            }
            if(isPureNum) {
                res.add(Integer.parseInt(input));
                map.put(input, res);
                return res;
            } else {
                map.put(input, res);
                return res;
            }
        }
    }

  • 0
    H

    without cache time complexity should be O(n!) and n is the number of operators.


Log in to reply
 

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