LeetCode 1268. 搜索推荐系统

LeetCode 1268. 搜索推荐系统

输入一个词典，然后输入一个单词，对于单词的每一个前缀，输出字典中以这个前缀开始的单词的字典序最小的 3 个单词。词典长度 1000，词典中每个单词的长度 20000，目标单词长度 1000.

这道题目开始的想法是字典树。可是数据集的范围太大，字典树占用空间太大。然而也没有想到什么好的方法，最后还是用常规的字典树写了一下，竟然过了。

#include <iostream>
#include <vector>
#include <string>
#include <stack>

using namespace std;
using VS = vector<string>;
struct TrieTree
{
  char value;
  bool is_end;
  TrieTree *children[26];
  TrieTree()
  {
    for (int i = 0; i < 26; i++) children[i] = nullptr;
    is_end = false;
  }
};

void insert_word(TrieTree *root, string s)
{
  for (auto x: s)
    {
      int pos = x - 'a';
      if (nullptr != root->children[pos])
      {
	root = root->children[pos];
      }
      else
      {
	TrieTree *tmp = new TrieTree();
	tmp->value = x;
	root->children[pos] = tmp;
	root = tmp;
      }
    }
  root->is_end = true;
}

void print_tree(TrieTree *root, string s, vector<string> &words)
{
  for (int i = 0; i < 26; i++)
    {
      TrieTree *child = root->children[i];

      if (nullptr != child)
      {
	if (child->is_end) {
	  if (words.size() >= 3) return;
	  words.push_back(s + child->value);
	}
	print_tree(child, s + child->value, words);
      }
    }
}

void prefix_three(TrieTree *root, string s, vector<string> &words, string target)
{
  for (size_t i = 0; i < target.size(); i++)
    {
      int pos = target[i] - 'a';
      TrieTree *child = root->children[pos];
      if (nullptr == child) return;
      root = child;
    }
  if (root->is_end) words.push_back(target);
  print_tree(root, target, words);
}
class Solution {
public:
  vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
    TrieTree tree;

    for (auto p : products)
      {
      insert_word(&tree, p);
      }

    vector<vector<string>> result;

    for (size_t i = 0; i < searchWord.size(); i++)
      {
      vector<string> words;
      prefix_three(&tree, "", words, searchWord.substr(0, i + 1));
      result.push_back(words);
      }

    return result;
  }
};

int main(void)
{
  Solution a;
  // vector<string> products {
  // 			   "mobile","mouse","moneypot","monitor","mousepad"
  // }
  // ;
  // string word = "mouse";
  vector<string> products  {"code","codephone","coddle","coddles","codes"
  };
  string word = "coddle";

  vector<vector<string>> result = a.suggestedProducts(products, word);
  for (size_t i = 0; i < result.size(); i++)
    {
      vector<string> x = result[i];
      cout << "prefix: " << word.substr(0, i + 1) << endl;

      for (auto y : x)
      {
	cout << y << " ";
      }
      cout << endl;
    }

  return 0;
}

可见 LeetCode 上的数据是很弱的。之前已经遇到过很多类似的情况。不过，至少这道题目练习了一下字典树的写法。

然后看了一下题解，果然是字典树，不过有一些优化。由于我们只需要字典序的前 3 个，为了更加方便地取得结果，我们可以把这 3 个单词保存在节点上，这样对每个单词前缀，我只需要找到对应的节点，然后把节点上的 3 个单词取出来就好了，而不用每次都去遍历子树。由于需要字典序最小的 3 个，所以可以维护一个大小为 3 的优先队列。另外，对于字典树的实现方式，节点中可以不用数组，直接使用 unordered_map 就好，实现也方便，也不会成为性能瓶颈。

struct TrieTree2
{
  priority_queue<string> words;
  unordered_map<char, TrieTree2*> children;
};

void insert_word2(TrieTree2 *root, string s)
{
  TrieTree2 *cur = root;

  for (auto x: s)
    {
      if (cur->children.find(x) == cur->children.end())
	{
	  cur->children[x] = new TrieTree2();
	}
      cur = cur->children[x];
      cur->words.push(s);
      if (cur->words.size() > 3) cur->words.pop();
    }
}

vector<vector<string>> get_words2(TrieTree2 *root, string s)
{
  TrieTree2 *cur = root;
  vector<vector<string>> res;
  for (size_t i = 0; i < s.size(); i++)
    {
      vector<string> tmp;
      if (cur != nullptr)
	{
	  cur = cur->children[s[i]];

	  while(cur != nullptr && !cur->words.empty())
	    {
	      tmp.push_back(cur->words.top());
	      cur->words.pop();
	    }
	}
      reverse(tmp.begin(), tmp.end());
      res.push_back(tmp);
    }
  return res;
}

class Solution {
public:
  vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
    TrieTree2 *root = new TrieTree2();
    for (auto x: products) insert_word2(root, x);
    return get_words2(root, searchWord);
  }
};

对于基础题目还是需要多练习，实现方式、思路、优化等，自己的解题能力和代码能力还远远不够。

comments powered by Disqus