问了一个LintCode原题 add and search word,设计算法支持两个操作,一个是add一个字符串,一个是search某个字符串是否在目前的字典中。查找的串可能包含通配符‘.",匹配任意一个字符。用Trie Tree即可。 然后小哥问了一下如何在space和time之间trade off,这个问题我做题的时候就想过,因为这题有两种做法,一是建树时不把"."作为一个字符,而在搜索时碰到"."时搜索所有儿子节点。另外一种是建树时把"."加入到每个节点的儿子节点中,把所有包含"."的字符串也存在Trie Tree中。两种做法的区别在于,前者空间复杂度低,每次add时间复杂度是字符串长度,每次search时间复杂度是O(26^"."的个数);后者空间复杂度高,每次add时间复杂度是2的字符串长度次方,每次search时间复杂度是字符串长度。印度小哥表示挺满意的~
北京市 · 互联网 · 100-499人 · 成立18年 · 近3个月无招聘
公司全称
谷歌信息技术(中国)有限公司
上下班时间
-
联系方式
010-62505969
62505969
...更多
地址
北京市海淀区科学院南路2号院1号楼4、5、6、7层及8层801-806、808-814
简介
-