Java DP solution with comments and Recur with time complexity explanation


  • 0
    A

    Recursion:
    I was interested in the time complexity of this solution, aka why it was slow, and saw other posts mentioning O(2^n). For anyone who's curious about how they arrived at that - as I had trouble initially - here's the work:

    T(n) = T(n-1) + T(n-2) + T(n-3)...+ 1
    also, T(n-1) = T(n-2) + T(n-3)...+ 1

    So:
    T(n) = T(n-1) + T(n-2) + T(n-3)...+ 1
    = T(n-1) + T(n-1) // subbing in T(n-1) equation from above
    = 2 * T(n-1)
    = 4 * T(n-2)
    = ...
    = 2^n // since T(1) = 1

    Recur Solution

        public boolean wordBreak(String s, Set<String> wordDict) {
            if (s.isEmpty() || wordDict.isEmpty()) {
                return false;
            }
            if (wordDict.contains(s)) { return true; }
    
            return canBreak(0, s, wordDict);
        }
    
        private boolean canBreak(int ind, String str, Set<String> dict) {
            if (ind == str.length()) { return true; }
    
            for (int i = ind; i < str.length(); i++) {
                boolean isWord = dict.contains(str.substring(ind, i+1));
    
                if (isWord && canBreak(i+1, str, dict)) {
                    return true;
                }
            }
            return false;
        }
    

    DP Solution:

        public boolean wordBreak(String s, Set<String> wordDict) {
            if (s.isEmpty() || wordDict.isEmpty()) {
                return false;
            }
            if (wordDict.contains(s)) { return true; }
    
            boolean[] dp = new boolean[s.length()];        // Visited
            Stack<Integer> track = new Stack<>();          // Curr tokens, starts and ends
    
            for (int i = 0, prev = 0; i < s.length(); i++) {
                if (!dp[i]) {
                    boolean isWord = wordDict.contains(s.substring(prev, i + 1));
    
                    if (isWord && i == s.length()-1) {
                        return true;        // Ending token, return right away
    
                    } else if (isWord) {
                        dp[i] = true;        // Add to visited
                        track.push(prev);
                        track.push(i);
                        prev = i + 1;
    
                    } else if (!track.isEmpty() && i == s.length()-1) {
                        // Reset; End and tokenizing path is not breakable
                        // Retry from last tokenized spot
                        i = track.pop();        // End
                        prev = track.pop();     // Start
                    }
                }
            }
            return false;
        }
    

Log in to reply
 

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