美文网首页
472. 连接词

472. 连接词

作者: 来到了没有知识的荒原 | 来源:发表于2021-10-11 13:57 被阅读0次

472. 连接词

const int N = 100010;
int son[N][26];
int cnt[N], idx;
bool vis[N];

class Solution {
 public:
  void insert(string &s) {
    int p = 0;
    for (auto c : s) {
      int u = c - 'a';  // 确定分支
      if (!son[p][u]) son[p][u] = ++idx;
      p = son[p][u];
    }
    cnt[p] = 1;
  }
  bool query(string &s, int cur) {
    int p = 0;
    if (cur == s.size()) return true;
    if (vis[cur]) return false;
    for (int i = cur; i < s.size(); i++) {
      int u = s[i] - 'a';
      if (!son[p][u]) break;
      p = son[p][u];
      if (cnt[p]) {
        if (query(s, i + 1)) return true;
      }
    }
    vis[cur] = true;
    return false;
  }
  vector<string> findAllConcatenatedWordsInADict(vector<string> &words) {
    sort(words.begin(), words.end(),
         [](const string &a, const string &b) { return a.size() < b.size(); });
    memset(son, 0, sizeof son), memset(cnt, 0, sizeof cnt),
        memset(vis, 0, sizeof vis);
    idx = 0;

    vector<string> res;
    for (auto &s : words) {
      if (s.empty()) continue;
      if (query(s, 0)) res.push_back(s);
      insert(s);
      memset(vis, 0, sizeof vis);
    }

    return res;
  }
};

相关文章

  • 472. 连接词

    472. 连接词[https://leetcode-cn.com/problems/concatenated-wo...

  • (trie,dfs)472. 连接词

    472. 连接词[https://leetcode-cn.com/problems/concatenated-wo...

  • 472.晚安

    我想念你了 却不敢告诉你

  • 8.23 - hard - 91

    472. Concatenated Words 利用Trie做出一个TLE的版本。其实简单的利用recursion...

  • 472.笼恩

    把一只小鸟关在笼子里,然后这只小鸟很感恩把它关起来的人,这就叫笼恩。其实这只是一个比喻。我估计任何一只小鸟都不会因...

  • 语法俱乐部第十五章——对等从句

    1. 连接词 对等连接词——and、but、or,用来连接句子中两个对等的部分——单词或短#语亦或对等的从句。 2...

  • 幽默它不香吗 03丨 段子的基本公式

    关键点: 一、段子=铺垫+包袱 二、连接词 三、强化误导 四、重点的讲下铺垫与包袱,连接词在后面详细讲。 段子:在...

  • 连接词

    递进 moreover 此外 转折 yet 但是;然而

  • 连接词

    Bread-earner 挣钱养家的人 By-product 副产品 Capital-intensive 资本密集...

  • 连接词

    Refuse To

网友评论

      本文标题:472. 连接词

      本文链接:https://www.haomeiwen.com/subject/iygpnltx.html