# Java DP solution with comments and Recur with time complexity explanation

• 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;
}
``````

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