如何使用 Tries 计算 Leetcode 最长公共前缀的时间复杂度

Question

我正在努力提高我的问题解决能力，并使用 Trie 数据结构解决了 Leetcode“最长公共前缀”中的问题 #14。

我的解决方案运行时间为 106 毫秒，跑赢了 42.91%。但是，我不太确定如何找出解决方案的时间复杂度。

1. public class Solution
2. {
3.     public class TrieNode
4.     {
5.         public bool IsEndOfString = false;
6.         public TrieNode[]? Children;
7.         public int Visits = 0;
8.     }
9.     
10.     public class Trie
11.     {
12.         private const int AlphabetSize = 26;
13.         private TrieNode _root;
14.         private int _max = 0;
15.     
16.         public Trie()
17.         {
18.             _root = new TrieNode()
19.             {
20.                 Visits = -1,
21.                 Children = new TrieNode[AlphabetSize]
22.             };
23.         }
24.     
25.         public void Insert(string key)
26.         {
27.             TrieNode currentNode = _root;
28. 
29.             foreach (char c in key)
30.             {
31.                 int currentIndex = c - 'a';
32.     
33.                 if (currentNode.Children[currentIndex] is null)
34.                     currentNode.Children[currentIndex] = new TrieNode()
35.                     {
36.                         Children = new TrieNode[AlphabetSize]
37.                     };
38. 
39.                 currentNode = currentNode.Children[currentIndex];
40. 
41.                 currentNode.Visits++;
42.     
43.                 if (currentNode.Visits > _max)
44.                     _max = currentNode.Visits;
45.             }
46.     
47.             currentNode.IsEndOfString = true;
48.         }
49.     
50.         public List<string> FindAllPrefixes(string[] strs)
51.         {
52.             StringBuilder prefixBuilder = new StringBuilder();
53.             List<string> listOfPrefixes = new List<string>();
54.         
55.             foreach (string key in strs)
56.             {
57.                 TrieNode currentNode = _root;
58.         
59.                 foreach (char c in key)
60.                 {
61.                     var currentIndex = c - 'a';
62.                     if (currentNode.Children[currentIndex] is not null && currentNode.Children[currentIndex].Visits == _max)
63.                     {
64.                         prefixBuilder.Append((char) (currentIndex + 'a'));
65.                         currentNode = currentNode.Children[currentIndex];
66.                     }
67.                     else
68.                         break;
69.                 }
70.                 listOfPrefixes.Add(prefixBuilder.ToString());
71.                 prefixBuilder.Clear();
72.             }
73. 
74.             return listOfPrefixes;
75.         }
76.     }
77. 
78.     public string LongestCommonPrefix(string[] strs)
79.     {
80.         if (strs.Length == 1)
81.             return strs[0];
82. 
83.         Trie trie = new Trie();
84. 
85.         foreach (string str in strs)
86.             trie.Insert(str);
87.         
88.         List<string> listOfPrefixes = trie.FindAllPrefixes(strs);
89.         listOfPrefixes.Sort((a, b) => b.Length.CompareTo(a.Length));
90.         string longestPrefix = listOfPrefixes[0];
91.         
92.         foreach (string str in strs)
93.         {
94.             if (!str.StartsWith(longestPrefix))
95.                 return string.Empty;
96.         }
97. 
98.         return longestPrefix;
99.     }
100. }

我的猜测是这样的：

• 第 88 行，应该是 O(n * m)，其中 n 是 strs 的数量，m 是 keys 的数量。
• 在第 89 行，O(k ^ 2) 其中 k 是前缀的数量。
• 在第 92 行，O(i) 其中 i 是 strs 的数量。
• 这留下了总的复杂性：

  O(n * m * K ^ 2 * i)

  如果我的解释不准确，请更正我的解释。

谢谢。