DFS with Path Memorizing Java Solution

• I write this method by what I learned from @mahdy in his post Decode Ways

Use a set to record all position that cannot find a match in dict. That cuts down the run time of DFS to O(n^2)

``````public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
// DFS
Set<Integer> set = new HashSet<Integer>();
return dfs(s, 0, dict, set);
}

private boolean dfs(String s, int index, Set<String> dict, Set<Integer> set){
// base case
if(index == s.length()) return true;
// check memory
if(set.contains(index)) return false;
// recursion
for(int i = index+1;i <= s.length();i++){
String t = s.substring(index, i);
if(dict.contains(t))
if(dfs(s, i, dict, set))
return true;
else
}
return false;
}
}
``````

• Why is the complexity O(n^2)?

• good set for memorization

• @Neal_Yang
Say length of the string s = N, when dfs() is called for first time, it takes O(N) to find a valid sub-string t.
Then, we call dfs(s, i, dict, set) and all invalid index will be kept in set when it returns.
The remaining loop iterations take O(N), since we simply look up hash tables.
So, the time complexity = O(N) + O(f(N-i)) + O(N) = O(2N + f(N-1)) = O(2N + 2(N-1) + ... + 1) = O(N^2).

• Say length of the string s = N, when dfs() is called for first time, it takes O(N) to find a valid sub-string t.

Why not just O(n), since for each index, we only check for once.

• @siyang3

``````if(dict.contains(t))
if(dfs(s, i, dict, set))
return true;
else
``````

can be shortened to

``````if(dict.contains(t) && dfs(s,i,dict,set)) {
return true;
}
``````

• @liu971 But we may visited the same index again and again. Only improvement is that we don't need to valid the S.substring(index).

• @abagogogo I think for O(N^2), you're assuming that the `substring()` function takes O(1) time, but I think it takes O(N) time. So since it takes O(N) to create each (sub-)string, would take O(N^2) to find a valid sub-string t starting from the first char, and would take O(N^3) when the recursion circles back and check sub-string t from all starting points.

Using a prefix tree makes the time for string comparison between 2 strings and the time to find a valid-sub-string t starting from the first char both O(N), since we're are comparing all words with the same prefix at each step. This makes total run time O(N^2).

``````class Solution {
private:
class trie {
public:
vector<trie*> next;
bool isword;
trie() {
next.resize(26,nullptr);
isword=false;
}
~trie() {
for (int i=0; i<26; i++) delete next[i];
}
};

trie *root;

void buildTrie(vector<string>& wordDict) {
root = new trie();
trie *cur;
for (string word:wordDict) {
cur=root;
for (char c:word) {
if (!cur->next[c-'a']) cur->next[c-'a']=new trie();
cur=cur->next[c-'a'];
}
cur->isword=true;
}
}

bool dfs(string s, int idx, unordered_set<int>& visited) {
if (idx==s.length()) return true;
if (visited.count(idx)) return false;
else visited.insert(idx);

trie *cur=root;
for(int i=idx; i<s.length(); i++) {
char c=s[i];
if (!cur->next[c-'a']) return false;
cur=cur->next[c-'a'];

if (cur->isword && dfs(s,i+1,visited)) return true;
}
return false;
}

public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<int> visited;
buildTrie(wordDict);
return dfs(s,0,visited);
}
};
``````

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