Concise C++ solution


  • 0
    S

    use DFS to search result, use DP idea(memorized) to do pruning.
    AC 60 ms.

      class Solution {
        public:
            bool wordBreakImpl(string s, unordered_set<string> &dict, vector<string> &path, unordered_map<string, bool> &memory, vector<string> &ret)
            {
                if(s.size() == 0)
                {
                    string one;
                    for(int i = 0; i < path.size(); i++)
                    {
                        if(i == 0)
                            one = path[i];
                        else
                            one += " " + path[i];
                    }
                    ret.push_back(one);
                    return true;
                }
                else
                {
                    if(memory.find(s) != memory.end() && memory[s] == false)
                        return false;
                    
                    int result = false;
                    for(int i = 0; i < s.size(); i++)
                    {
                        string word = s.substr(0, i+1);
                        if(dict.find(word) != dict.end())
                        {
                            path.push_back(word);
                            
                            if(wordBreakImpl(s.substr(i+1), dict, path, memory, ret))
                                result = true;
                            
                            path.pop_back();
                        }
                    }
                    memory[s] = result;
                    return memory[s];
                }
            }
            
            vector<string> wordBreak(string s, unordered_set<string> &dict) {
                
                vector<string> ret;
                vector<string> path;
                unordered_map<string, bool> memory;
                wordBreakImpl(s, dict, path, memory, ret);
                
                return ret;
            }
        };

  • 0
    B

    I tried your code in oj system and it is really fast. But when I tried it using eclipse, it is extremely slow. I am wondering do you know why this happens?


Log in to reply
 

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