@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);
}
};