从Leetcode 每日一题练习继续讨论：
3043. 最长公共前缀的长度
3043. Find the Length of the Longest Common Prefix
题解
题目中的数组要求求最长公共前缀，考虑到每个数组中的不同数字之间也可能存在公共前缀，为了避免对字符串进行重复遍历，可以使用字典树。字典树充分利用了数字每一位的信息，非常适用于类似本题目的求前缀等场景下，还有一道经典题目是求数组中任意两个数字的最大异或和，也可以使用字典树求解，利用异或运算异或两次后会回到数字本身的特性，用数字的二进制形式构造字典树，充分利用每个二进制位的信息，通过贪心尽量将每一位置为1，最终找到最大异或和，可参考P4551 最长异或路径
本题在对两个数组构建好两棵字典树后，对字典树同时进行dfs，依次选取每一层中相同的字符对应的子节点进行遍历，直到在某一层无法找到共同字符为止。用一个变量保存遍历到的树的最大深度即为最长公共前缀的长度。
代码
#pragma GCC optimize("O3", "unroll-loops")
const int TREESIZE = 10;
struct TrieNode{
TrieNode *children[TREESIZE];
bool isEndOfWord;
TrieNode(): isEndOfWord(false){
for (int i = 0;i<TREESIZE;++i){
children[i] = nullptr;
}
}
};
class Trie{
public:
TrieNode *root;
Trie(){root = new TrieNode();}
void insert(const string& word){
TrieNode* node = root;
for(char c : word){
if (node->children[c-'0'] == nullptr){
node->children[c-'0'] = new TrieNode();
}
node = node->children[c-'0'];
}
node->isEndOfWord = true;
}
~Trie() {
function<void(TrieNode*)> deleteTrie = [&](TrieNode* node) {
if(node == nullptr) return;
for(int i = 0; i < TREESIZE; ++i){
if(node->children[i] != nullptr){
deleteTrie(node->children[i]);
}
}
delete node;
};
deleteTrie(root);
};
};
class Solution {
public:
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
ios::sync_with_stdio(false);
Trie *trie1 = new Trie();
for (int num : arr1){
string numstr = to_string(num);
trie1->insert(numstr);
}
Trie *trie2 = new Trie();
for (int num : arr2){
string numstr = to_string(num);
trie2->insert(numstr);
}
int result = 0;
dfs(trie1->root, trie2->root, 0, result);
return result;
}
void dfs(TrieNode* root1,TrieNode* root2, int depth, int& result){
result = max(result, depth);
for(int i=0;i<TREESIZE;i++){
if (root1->children[i] != nullptr && root2->children[i] != nullptr){
cout<< i;
dfs(root1->children[i],root2->children[i],depth+1,result);
}
}
}
};