--!native
--!nonstrict
--!optimize 2
-- Compiled with roblox-ts v2.3.0
local Trie
do
	Trie = setmetatable({}, {
		__tostring = function()
			return "Trie"
		end,
	})
	Trie.__index = Trie
	function Trie.new(...)
		local self = setmetatable({}, Trie)
		return self:constructor(...) or self
	end
	function Trie:constructor()
		self.root = {
			children = {},
			isEnding = false,
		}
	end
	function Trie:insert(word)
		local current = self.root
		for index = 1, #word do
			local byte = string.byte(word, index)
			local nextInLine = current.children[byte]
			if not nextInLine then
				local _children = current.children
				nextInLine = {
					children = {},
					isEnding = false,
				}
				local _nextInLine = nextInLine
				_children[byte] = _nextInLine
			end
			current = nextInLine
		end
		current.isEnding = true
	end
	function Trie:search(word)
		local current = self.root
		for index = 1, #word do
			local _children = current.children
			local _arg0 = (string.byte(word, index))
			local nextInLine = _children[_arg0]
			if not nextInLine then
				return false
			end
			current = nextInLine
		end
		return current.isEnding
	end
	function Trie:startsWith(prefix)
		local current = self.root
		for index = 1, #prefix do
			local _children = current.children
			local _arg0 = (string.byte(prefix, index))
			local nextInLine = _children[_arg0]
			if not nextInLine then
				return false
			end
			current = nextInLine
		end
		return true
	end
end
return {
	Trie = Trie,
}