C艹 concise solution, use hash map


  • 0
    V
    class Solution {
    public:
      vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        sort(words.begin(), words.end(),
            [](const string& lhs, const string& rhs) {
          return lhs.length() < rhs.length();
        });
        words_.insert(words.begin(), words.end());
        vector<string> result;
        for (const string& word : words) {
          if (word.empty()) {
            continue;
          }
          words_.erase(word);
          if (dfs(word)) {
            result.emplace_back(word);
          }
          words_.insert(word);
          visited_[word] = true;
        }
        return result;
      }
    private:
      bool dfs(const string& word) {
        if (visited_.count(word)) {
          return visited_[word];
        }
        for (size_t i = 1; i < word.size(); ++i) {
          if (words_.count(word.substr(0, i)) && dfs(word.substr(i))) {
            return visited_[word] = true;
          }
        }
        return visited_[word] = word.empty();
      }
      unordered_map<string, bool> visited_;
      unordered_set<string> words_;
    };
    

Log in to reply
 

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