1、描述

根據幾個單詞，構造一個前綴樹，再給定一個單詞p,判斷p是否屬于s的前綴
輸入：vec = {“hello”, “world”, “hey”, “hi”} p = “hell”
輸入：yes

2、notes

就直接構造

3、code

#include <iostream>
#include <vector>
#include <cstring>using namespace std;struct TrieNode {TrieNode* children[26];bool isEnd;TrieNode() {memset(children, 0, sizeof(children));isEnd = false;}
};void insert(TrieNode* root, string word) {TrieNode* node = root;for (char c : word) {int index = c - 'a';if (!node->children[index]) {node->children[index] = new TrieNode();}node = node->children[index];}node->isEnd = true;
}TrieNode* buildTrie(vector<string>& words) {TrieNode* root = new TrieNode();for (string word : words) {insert(root, word);}return root;
}bool isPrefix(TrieNode* root, string prefix) {TrieNode* node = root;for (char c : prefix) {int index = c - 'a';if (!node->children[index]) {return false;}node = node->children[index];}return true;
}int main() {vector<string> words = {"hello", "world", "hi", "hey"};TrieNode* root = buildTrie(words);string s = "hello, world, hi, hey";string p1 = "worldi";string p2 = "hell";string p3 = "abc";if (isPrefix(root, p1)) {cout << p1 << " is a prefix of " << s << endl;} else {cout << p1 << " is NOT a prefix of " << s << endl;}return 0;
}