Solution waiting your comments (16 ms)


  • 0
    L

    Could anayone review how much this solution effective in worst case?

    class Solution {
    private:
    
        void getVector(string& s, multimap<int, string> &mmap, vector<string>& res, int pos, string str) {
            if (pos > s.length()) {
                return;
            }
            else if (pos == s.length())
            {
                res.push_back(str);
                return;
            } else if (!str.empty()) {
                str.append(" ");
            }
            pair <multimap<int,string>::iterator, multimap<int,string>::iterator> ret;
            ret = mmap.equal_range(pos);
            for (multimap<int,string>::iterator it=ret.first; it!=ret.second; ++it) {
                string temp = str;
                temp.append(it->second);
                getVector(s, mmap, res, pos+it->second.length(), temp);
            }
        }
        
    public:
        vector<string> wordBreak(string s, unordered_set<string> &dict) {
            multimap<int, string> mmap;
            bool start = false, end = false;
            int len = s.length();
            for (unordered_set<string>::iterator it = dict.begin(); it != dict.end(); ++it ) {
                size_t found = string::npos;
                while ((found = s.find(*it, found+1)) != string::npos) {
                    mmap.insert(pair<int,string>(found,*it));
                    if (found == 0) start = true;
                    if ((found + (*it).length()) == len) end = true;
                }
            }
            vector<string> res;
            if (start && end){
                string temp;
                getVector(s, mmap, res, 0, temp);
            }
            return res;
        }
    };

Log in to reply
 

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