Участник:S1td1kov/ConcatenatedWords

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/concatenated-words/

 
//follow my github https://github.com/RusS1103/Leetcode
 
const int ZERO = [](){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    return 0;
}();
 
class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        vector<string> res;
        if(words.empty()) {
            return res;
        }
        unordered_set<string> myset(words.begin(),words.end());
        if(myset.find("") != myset.end()) {
            myset.erase("");
        }
 
        for(auto w : words) {
            if(find(myset,w,w)) {
                res.push_back(w);
            }
        }
        sort(res.begin(), res.end());
        return res;
    }
    bool find(unordered_set<string>& myset, string word, string& original){
        if(word.length() > 0 && word != original && myset.find(word) != myset.end()) {
                return true;
        }
        int len = word.length();
        for(int i = 1; i <= len; i++) {
            string subword = word.substr(0,i);
            string other = word.substr(i);
            if(myset.find(subword)!=myset.end()) {
                 if(find(myset, other, original)) {
                     return true;
                 }
            }
        }
        return false;
    }
};