Evolve from brute force to optimal, a review of all solutions


  • 17
    1. Recursion O(2^n)
      T(n) = T(n-1)+T(n-2)+...+T(1)
      => T(n+1) = T(n)+T(n-1)+T(n-2)+...+T(1)
      =>T(n+1) = 2T(n)
        bool wordBreak(string s, unordered_set<string>& wordDict) {
            return canBrk(0,s,wordDict);    
        }
        bool canBrk(int start, string& s, unordered_set<string>& wordDict) {
            int n = s.size();
            if(start == n) return 1;
            string sub;
            for(int i = start; i<n; i++) if(wordDict.count(sub+=s[i]) && canBrk(i+1,s,wordDict)) return 1;
            return 0;
        }
    
    1. O(n^2) DFS with Memoization. There is redundancy in #1. A substr may be checked multiple times. We can cache the result by memoization. This is the optimal solution.
        bool wordBreak(string s, unordered_set<string>& wordDict) {
            vector<char> mem(s.size(),-1);
            return canBrk(0,s,wordDict,mem);    
        }
        bool canBrk(int start, string& s, unordered_set<string>& wordDict,vector<char>& mem) {
            int n = s.size();
            if(start == n) return 1;
            if(mem[start]!= -1) return mem[start];
            string sub;
            for(int i = start; i<n; i++) if(wordDict.count(sub+=s[i]) && canBrk(i+1,s,wordDict,mem)) return mem[start] = 1; 
            return mem[start] = 0;
        }
    
    1. O(n^2) dp. For dp problems, many times we go into iterative dp directly without even thinking about dfs. This is a great example showing that dfs is better than dp. DFS returns as soon as it finds one way to break the word while dp computes if each substring starting/ending at i is breakable. The test cases of this problem do not show it but it is shown in a similar problem Concatenated Words.
        bool wordBreak(string s, unordered_set<string>& wordDict) {
            int n = s.size();
            vector<bool> dp(n+1);
            dp[n]=1;
            for(int i=n-1;i>=0;i--) {
                string sub;
                for(int j=i;j<n;j++) if (dp[i] = wordDict.count(sub+=s[j]) && dp[j+1]) break;
            }
            return dp[0];    
        }
    
    1. BFS, O(n^2) BFS may be better than dp. In dp, for each index i, it checks if the substr starting at i can break. However, if the substr ending before i cannot break, then we do not have to check i. But this is the nature of dp, we visit all the states and derive the next state according to previous states and I don't find a way to improve the dp solution. BFS always starts from a valid index and may visit fewer states. This is similar to Perfect Squares. But BFS is not guaranteed to be better than dp. If every index is a valid state, then BFS visits the same number of states as dp. The inner for loop of BFS looks more expensive than the inner for loop of dp. So I think which is better is case by case. In general, both BFS and dp visit all the states and are less efficient than dfs.
        bool wordBreak(string s, unordered_set<string>& wordDict) {
            queue<int> q({0});
            unordered_set<int> vstd;
            int n = s.size();
            while(!q.empty()) {
                int start = q.front();
                q.pop();
                if(vstd.count(start)) continue;
                vstd.insert(start);
                string sub;
                for(int i=start;i<n;i++) 
                    if(wordDict.count(sub+=s[i])) {
                        q.push(i+1);
                        if(i+1 == n) return 1;    
                    }
            }
            return 0;    
        }
    

  • 0
    K

    @yu6
    Thanks, the thinking process is exactly what I am looking for.

    I also come up a improved brute force idea..

    The time complexity will be O(stringleng * dictionary's size)..
    However, my solution doesn't guarantee "shortest" path, that's say dp[i] may be constructed serval times.. So I think BFS might be the optimal solution for this problem.

        public boolean wordBreak(String s, Set<String> wordDict) {
            if(s == null) return true;
            if(wordDict == null || (wordDict.size() == 0 && s.length() != 0)) return false;
            
            int size = s.length();
            boolean [] dp = new boolean [size+1];
            /*
                The dp[i] represent if substring 0->i(exclusive) could be break into the words in dict
                dp[0] is true;
            */
            dp[0] = true;
            
             for(int i = 0; i <= size; i++) {
                if(dp[i] == true) {
                    for(String word : wordDict) {
                        if(i + word.length() > size) {
                            continue;
                        }
                        if(s.substring(i, i+ word.length()).equals(word)) {
                            dp[i+word.length()] = true;
                        }
                    }
                }
            }
        
            return dp[size];
        }
    

  • 0

    @kun5 Glad it helps. I just update the post with more thoughts. Now I am convinced DFS with memoization is the most efficient solution.


  • 0
    A

    @yu6 Hi do you mind to explain what are the very first few lines?
    T(n) = T(n-1)+T(n-2)+...+T(1)
    => T(n+1) = T(n)+T(n-1)+T(n-2)+...+T(1)
    =>T(n+1) = 2T(n)


  • 0

Log in to reply
 

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