DFS with Path Memorizing Java Solution


  • 27
    S

    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
                        set.add(i);
            }
            set.add(index);
            return false;
        }
    }
    

  • 0
    M

    Why is the complexity O(n^2)?


  • 0
    N

    good set for memorization


  • 4
    A

    @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).


  • 0
    L

    @abagogogo said in DFS with Path Memorizing Java Solution:

    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.


  • 0
    M

    @siyang3

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

    can be shortened to

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

    set.add(i) is redundant since you are already adding it at the end before returning false.


  • 0
    K

    @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).


  • 2
    B

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

Log in to reply
 

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