A solution using BFS


  • 72
    G

    People have posted elegant solutions using DP. The solution I post below using BFS is no better than those. Just to share some new thoughts.

    We can use a graph to represent the possible solutions. The vertices of the graph are simply the positions of the first characters of the words and each edge actually represents a word. For example, the input string is "nightmare", there are two ways to break it, "night mare" and "nightmare". The graph would be

    0-->5-->9

    |__ __ _^

    The question is simply to check if there is a path from 0 to 9. The most efficient way is traversing the graph using BFS with the help of a queue and a hash set. The hash set is used to keep track of the visited nodes to avoid repeating the same work.

    For this problem, the time complexity is O(n^2) and space complexity is O(n), the same with DP. This idea can be used to solve the problem word break II. We can simple construct the graph using BFS, save it into a map and then find all the paths using DFS.

    bool wordBreak(string s, unordered_set<string> &dict) {
        // BFS
        queue<int> BFS;
        unordered_set<int> visited;
        
        BFS.push(0);
        while(BFS.size() > 0)
        {
            int start = BFS.front();
            BFS.pop();
            if(visited.find(start) == visited.end())
            {
                visited.insert(start);
                for(int j=start; j<s.size(); j++)
                {
                    string word(s, start, j-start+1);
                    if(dict.find(word) != dict.end())
                    {
                        BFS.push(j+1);
                        if(j+1 == s.size())
                            return true;
                    }
                }
            }
        }
        
        return false;
    }

  • 0
    R

    Can you give some more comments in your code?


  • 0
    M

    That is what I really need. Thx


  • 0
    D

    Can you give some explainations of your code?
    Thanks in advance.


  • 43
    D

    Nice solution! I think the basic idea here is same as DP:probe based on previous successful match

    I made a Java implementation based on your BFS idea

    public boolean wordBreak(String s, Set<String> dict) {
        if (dict.contains(s)) return true;
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(0);
        // use a set to record checked index to avoid repeated work.
        // This is the key to reduce the running time to O(N^2).
        Set<Integer> visited = new HashSet<Integer>();
        visited.add(0);
        while (!queue.isEmpty()) {
            int curIdx = queue.poll();
            for (int i = curIdx+1; i <= s.length(); i++) {
                if (visited.contains(i)) continue;
                if (dict.contains(s.substring(curIdx, i))) {
                    if (i == s.length()) return true;
                    queue.offer(i);
                    visited.add(i);
                }
            }
        }
        return false;
    }
    

  • 0
    G

    rewrote the explanation. Hope it helps.


  • 0
    B

    thx so much inspiring


  • 2
    B

    I think the idea is the same as backtracking, except this is breadth first. Not sure why BFS behaves better than DFS in the word break case..


  • 0
    H

    About word break II, would you please explain how to use DFS to find all the solutions? I use brute force after I get the graph by BFS, as far as I know. Thank you.


  • 8

    Damn clever idea!!! The code can still be optimized if we record the maximum and minimum length of the words in wordDict and only traverse the places within the minimum and maximum length.

    bool wordBreak(string s, unordered_set<string>& wordDict) {
        for (string word : wordDict) {
            minlen = min(minlen, (int)word.length());
            maxlen = max(maxlen, (int)word.length());
        }
        queue<int> toVisit;
        unordered_set<int> isVisited;
        toVisit.push(0);
        while (!toVisit.empty()) {
            int start = toVisit.front(); 
            toVisit.pop();
            if (isVisited.find(start) == isVisited.end()) {
                isVisited.insert(start);
                for (int i = start + minlen - 1; i < min(start + maxlen, (int)s.length()); i++) {
                    if (wordDict.find(s.substr(start, i - start + 1)) != wordDict.end()) {
                        if (i + 1 == s.length()) return true;
                        toVisit.push(i + 1);
                    }
                }
            }
        }
        return false;
    }

  • 0
    S

    I think this solution is the modified version of the DP one


  • 0
    Z

    pruning function: " if(visited.find(start) == visited.end()) "


  • 0
    Z

    An answer using DFS with pruning function:

    bool wordBreak(string s, unordered_set<string>& wordDict) {
        if(s.size()<=0){
            return false;
        }
        
        ///< some strategy that might be helpful:
        int longestWord = 0;
        int shortestWord = INT_MAX;
        for(string word:wordDict){
            longestWord = max(longestWord,int(word.size()) );
            shortestWord = min(shortestWord, int(word.size()));
        }
        
        
        bool res=false;
        unordered_set<int> visited;
        ///< this is general DFS with pruning function
        wordB(s, wordDict, 0, res, longestWord,shortestWord,visited);
        return res;
    }
    
    ///< this is general DFS with pruning function
    void wordB(string& s, unordered_set<string>& wordDict, int left, bool& res, int longestWord,int shortestWord,unordered_set<int>& visited){
        if(left >= s.size()){
            res = true;
            return;
        }
        for(int i=left+shortestWord-1; (i-left<longestWord) && i<s.size(); i++){
            ///< the pruning function : " visited.find(i)==visited.end() "
            if(visited.find(i)==visited.end() && wordDict.count(s.substr(left,i-left+1)) >0){
                visited.insert(i);
                wordB(s, wordDict, i+1,res, longestWord,shortestWord,visited);    
            }
        }
    }

  • 1

    @bboczeng It's not like DFS. This BFS is just a optimized DP which avoids irrelevant states.


  • 0

    In my mind, DFS should be the natural choice for this kind of problem. It's permutation + subset + infinite elements indeed. However, there is test case preventing we use DFS. So I assume the purpose of this problem is forcing us to go for DP.

    Here is what I thought at the very first. Of course, it's TLE...

        public boolean wordBreak(String s, Set<String> wordDict) {
            return doBreak(s, new StringBuilder(), wordDict.toArray(new String[0]));
        }
    
        private boolean doBreak(String s, StringBuilder path, String[] dict) {
            if (path.length() > s.length()) return false;       // terminate early
            if (!s.startsWith(path.toString())) return false;   // terminate early
            if (path.length() == s.length()) return true;
    
            for (String word : dict) {
                if (doBreak(s, path.append(word), dict))
                    return true;
                path.delete(path.length() - word.length(), path.length());
            }
            return false;
        }
    

  • 2
    V

    @cdai
    DFS with memoization should work. My code passed OJ

    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string>& wordDict) {
            unordered_map<int,bool> cache;
            bool isWordBreakPossible = wordBreakUtil(0, s, wordDict, cache);
            return(isWordBreakPossible);
        }
        
        bool wordBreakUtil(int pos, string &s, unordered_set<string>& wordDict, unordered_map<int,bool> &cache) {
            if(pos >= s.length()) {
                return true;
            }
            
            if(cache.find(pos) != cache.end()) {
                return(cache[pos]);
            }
            
            string currWord="";
            bool isRemainingWordPresent = false;
            for(int i=pos; i<s.length(); i++) {
                currWord.push_back(s[i]);
                if(wordDict.find(currWord) != wordDict.end()) {
                    isRemainingWordPresent = wordBreakUtil(i+1, s, wordDict, cache);
                    if(isRemainingWordPresent == true) {
                        break;
                    }
                }
            }
            cache[pos] = isRemainingWordPresent;
            return(isRemainingWordPresent);
        }
    };
    

  • 0
    V

    @GuaGua
    Very novel way of thinking. My first instinct is always DFS. I guess BFS is more interesting way to solve this problem.


  • 0
    H

    why need visited here? there is no repeat work... can anyone explain? thx


  • 0
    F

    @huijun The visited array will keep it from revisiting the same nodes. For example, a String "aaaaa", and dict ["a","aa","aaa"]. When we visiting index 0, we will add index 1,2,3 into the queue. Then in the second iteration, we pop out index 1. Now if we dont have visited array, we will add index 2 and index 3 again into the queue. This will cause lots of repeated calculations. The runtime will become O(n^n) {correct me if I am wrong.}


  • 1
    C

    I have tried the genius method in some cases and it comes out TLE...


Log in to reply
 

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