My 16ms solution with dictionary tree data structure.


  • 0
    Z
    class Solution {
    public:
      vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        dict_tree_node *root = new dict_tree_node();
        init_dict_tree(root, wordDict);
    
        ans.clear();
        if (quick_check(s, root))
          search(s, 0, root, "");
    
        clean(root);
        return ans;
      }
    
    private:
      static const int word_size = 26;
      vector<string> ans;
      struct dict_tree_node {
        bool is_word;
        dict_tree_node* next[word_size];
        dict_tree_node() {
          is_word = false;
          fill(next, next + word_size, nullptr);
        }
      };
    
      bool quick_check(const string &source, dict_tree_node *root) {
        vector<bool> visit(source.size() + 1);
        fill(visit.begin(), visit.end(), false);
        visit[0] = true;
        for (int i = 0; i < source.size(); i++) {
          if (visit[i]) {
            dict_tree_node *node = root;
            for (int j = i; j < source.size(); j++) {
              int char_index = source[j] - 'a';
              if (node->next[char_index] == nullptr)break;
              node = node->next[char_index];
              if (node->is_word) {
                visit[j + 1] = true;
              }
            }
          }
        }
        return visit[source.size()];
      }
    
      void search(const string &source, int index, dict_tree_node *root, string partial) {
        if (index == source.size()) {
          ans.push_back(partial);
          return;
        }
        dict_tree_node *node = root;
        for (int i = index; i < source.size(); i++) {
          int char_index = source[i] - 'a';
          if (node->next[char_index] == nullptr)break;
          node = node->next[char_index];
          if (node->is_word) {
            string word = source.substr(index, i + 1 - index);
            search(source, i + 1, root, partial == "" ? word : partial + " " + word);
          }
        }
      }
    
      void clean(dict_tree_node *root) {
        for (int i = 0; i < word_size; i++) {
          if (root->next[i])clean(root->next[i]);
        }
        delete root;
      }
      void add(dict_tree_node *root, string s) {
        for (int i = 0; i < s.size(); i++) {
          int index = s[i] - 'a';
          if (root->next[index] == nullptr) {
            root->next[index] = new dict_tree_node();
          }
          root = root->next[index];
        }
        root->is_word = true;
      }
    
      void init_dict_tree(dict_tree_node *root, const unordered_set<string> &wordDict) {
        for (string word : wordDict) {
          add(root, word);
        }
      }
    };

Log in to reply
 

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