4 ms c++ solution


  • -1
    Y
    class Solution {
    public:
        void wordAux(string s, unordered_set<string>& wordDict, int start, const string& curString, vector<string>& result, int minLen, int maxLen)
        {
            if(start >= s.size())
            {
                result.push_back(curString);
                return;
            }
            for(int len = minLen; start + len <= s.size() && len <= maxLen; len++)
            {
                string next = s.substr(start, len);
                if(wordDict.find(next) != wordDict.end())
                {
                    string temp = curString;
                    if(temp.size() > 0)
                    {
                        temp.push_back(' ');
                    }
                    temp.append(next);
                    wordAux(s, wordDict, start+len, temp, result, minLen, maxLen);
                }
            }
        }
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            vector<string> result;
            string curString = "";
            int minLen = INT_MAX;
            int maxLen = 0;
            bool alphaTable[26];
            memset(alphaTable, 0, sizeof(alphaTable));
            for(auto it = wordDict.begin(); it != wordDict.end(); it++)
            {
                maxLen = max(maxLen, (int)(it->size()));
                minLen = min(minLen, (int)(it->size()));
                for(int i = 0; i < it->size(); i++)
                {
                    alphaTable[it->at(i)-'a'] = true;
                }
            }
            bool flag = false;
            for(int i = 0; i < s.size(); i++)
            {
                if(!alphaTable[s[i]-'a']) return result;
                if(wordDict.find(s.substr(i, s.size()-i)) != wordDict.end())
                {
                    flag = true;
                }
            }
            if(!flag)
            {
                return result;
            }
            wordAux(s, wordDict, 0, curString, result, minLen, maxLen);
            return result;
        }
    };

Log in to reply
 

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