-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path0720-LongestWordInDictionary.cs
59 lines (52 loc) · 1.72 KB
/
0720-LongestWordInDictionary.cs
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
//-----------------------------------------------------------------------------
// Runtime: 112ms
// Memory Usage: 33.1 MB
// Link: https://leetcode.com/submissions/detail/351895712/
//-----------------------------------------------------------------------------
using System.Collections.Generic;
namespace LeetCode
{
public class _0720_LongestWordInDictionary
{
public string LongestWord(string[] words)
{
var root = new Trie() { Finished = true };
foreach (var word in words)
{
var current = root;
foreach (var ch in word)
{
if (current.Children[ch - 'a'] == null)
current.Children[ch - 'a'] = new Trie();
current = current.Children[ch - 'a'];
}
current.Finished = true;
current.Word = word;
}
var result = string.Empty;
var stack = new Stack<Trie>();
stack.Push(root);
while (stack.Count > 0)
{
var node = stack.Pop();
if (node.Finished)
{
if (node.Word.Length >= result.Length)
result = node.Word;
for (int i = 0; i < 26; i++)
{
if (node.Children[i] != null)
stack.Push(node.Children[i]);
}
}
}
return result;
}
public class Trie
{
public Trie[] Children = new Trie[26];
public bool Finished = false;
public string Word = string.Empty;
}
}
}