3043. Find the Length of the Longest Common Prefix
Tags:
Medium
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Time and space complexity
Approach - Implement using trie
1class TrieNode {
2 children: Record<string, TrieNode>;
3 is_end_of_word: boolean;
4
5 constructor() {
6 this.children = {};
7 this.is_end_of_word = false;
8 }
9}
10
11class Trie {
12 private root: TrieNode;
13
14 constructor() {
15 this.root = new TrieNode();
16 }
17
18 insert(word: string): void {
19 let node = this.root;
20 for(const char of word) {
21 if(!node.children[char]) {
22 node.children[char] = new TrieNode();
23 }
24 node = node.children[char];
25 }
26 node.is_end_of_word = true;
27 }
28
29 findLongestPrefix(word: string): number {
30 let node = this.root;
31 let length = 0;
32
33 for(const char of word) {
34 if(!node.children[char]) break;
35 node = node.children[char];
36 length++;
37 }
38
39 return length;
40 }
41}
42
43function findLongestCommonPrefix(arr1: number[], arr2: number[]): number {
44 const trie = new Trie();
45
46 for(const num of arr1) {
47 trie.insert(num.toString());
48 }
49
50 let max_length = 0;
51 for(const num of arr2) {
52 const prefix_length = trie.findLongestPrefix(num.toString());
53 max_length= Math.max(max_length, prefix_length);
54 }
55
56 return max_length;
57}