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
|
#!/usr/bin/env ruby
def assert_equal(expected, actual)
raise "expected: #{expected.inspect}, actual: #{actual.inspect}" unless expected == actual
end
LETTER_DIGIT_MAPPING = {
'a' => 2,
'b' => 2,
'c' => 2,
'd' => 3,
'e' => 3,
'f' => 3,
'g' => 4,
'h' => 4,
'i' => 4,
'j' => 5,
'k' => 5,
'l' => 5,
'm' => 6,
'n' => 6,
'o' => 6,
'p' => 7,
'q' => 7,
'r' => 7,
's' => 7,
't' => 8,
'u' => 8,
'v' => 8,
'w' => 9,
'x' => 9,
'y' => 9,
'z' => 9,
}
DIGIT_TO_LETTER = {
2 => 'abc',
3 => 'def',
4 => 'ghi',
5 => 'jkl',
6 => 'mno',
7 => 'pqrs',
8 => 'tuv',
9 => 'wxyz',
}
class Node
attr_reader :value, :children
def initialize(value, children = [])
@value = value
@children = children
end
def inspect
"(#{value},#{children.map(&:inspect).join(",")})"
end
end
def trie_from(words)
trie = {}
words.each do |word|
current = trie
word.chars.each do |char|
current[LETTER_DIGIT_MAPPING[char]] ||= {}
current = current[LETTER_DIGIT_MAPPING[char]]
end
if !current.key?(-1)
current[-1] = [word]
else
current[-1] << word
end
end
return trie
end
def words_from(trie, digits)
return [] if digits.empty?
current = trie[digits.shift]
return [] if current.nil?
matches = []
until digits.empty?
digit = digits.shift
current = current[digit]
break if current.nil?
if current.key?(-1)
matches << current[-1]
end
end
return matches.flatten
end
def solution(input_digits, valid_words)
trie = trie_from(valid_words)
matches = []
tail = 0
until tail == input_digits.length do
window = input_digits[0..tail]
words = words_from(trie, window)
matches << words unless words.empty?
tail += 1
end
return matches.compact
end
assert_equal [["act"], ["bat"], ["cat"]], solution([2, 2, 8], ["act", "bat", "cat", "acd", "test"])
|
