Can someone pls explain. Not getting this. Have tried best.
Anonymous User
38

Can someone please explain why the time complexity for below code will be : O(n^3) and not O(n!). Because in each for loop calling recursive function n times (substring length for that recursion call stack)

s = "leetcode", wordDict = ["l", "e", "ee", "t"]

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length()+1];
        return recursion(s, wordDict, 0, dp);
    }
    public boolean recursion(String s, List<String> wordDict, int start, boolean[] dp){
        if(start == s.length())//wordbreak of blank string in last (not choosing anything from the dictionary)
            return true;
        if(dp[start]==true)
            return true;
        for(int end = start + 1; end <= s.length(); end++){
            if(wordDict.contains(s.substring(start, end)) && recursion(s, wordDict, end, dp))
                return dp[end] = true;
        }
        return dp[start] = false;
    }
}```
Comments (1)