-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
109 lines (95 loc) · 2.49 KB
/
Solution.cs
File metadata and controls
109 lines (95 loc) · 2.49 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
public class Solution
{
public int LongestCommonPrefix(int[] arr1, int[] arr2)
{
//return UsingHashTable(arr1, arr2);
return UsingTrie(arr1, arr2);
}
private int UsingHashTable(int[] arr1, int[] arr2)
{
HashSet<int> set1 = [];
HashSet<int> set2 = [];
for (int i = 0; i < arr1.Length; i++)
{
int tmp = arr1[i];
while (tmp > 0)
{
set1.Add(tmp);
tmp /= 10;
}
}
for (int i = 0; i < arr2.Length; i++)
{
int tmp = arr2[i];
while (tmp > 0)
{
set2.Add(tmp);
tmp /= 10;
}
}
//Console.WriteLine($"[{string.Join(",", set1)}]");
//Console.WriteLine($"[{string.Join(",", set2)}]");
int ans = 0;
foreach (int num in set1)
{
if (set2.Contains(num))
{
ans = int.Max(ans, num);
}
}
return ans > 0 ? ans.ToString().Length : 0;
}
public class TrieNode
{
public TrieNode[] children = new TrieNode[10];
}
public class Trie
{
private readonly TrieNode root = new();
public void Insert(int num)
{
TrieNode node = root;
string numStr = num.ToString();
foreach (char digit in numStr.ToCharArray())
{
int idx = digit - '0';
if (node.children[idx] == null)
{
node.children[idx] = new TrieNode();
}
node = node.children[idx];
}
}
public int FindLongestPrefix(int num)
{
TrieNode node = root;
string numStr = num.ToString();
int len = 0;
foreach (char digit in numStr.ToCharArray())
{
int idx = digit - '0';
if (node.children[idx] == null)
{
break;
}
len++;
node = node.children[idx];
}
return len;
}
}
private int UsingTrie(int[] arr1, int[] arr2)
{
Trie trie = new();
foreach (int num in arr1)
{
trie.Insert(num);
}
int maxLen = 0;
foreach (int num in arr2)
{
maxLen = int.Max(maxLen, trie.FindLongestPrefix(num));
}
return maxLen;
}
}