Google电面

不就是两个字母吗？需要用trie吗？

m4reiiy 发表于 2015-1-25 11:40
trie和DFS不如hashmap快。。查找O(1)啊。。

其实LZ还可以用多层hashmap，一般可以省点内存什么的。。

怎么使用多层hashmap？

多谢分享～

mm豆 发表于 2015-4-9 13:49
怎么使用多层hashmap？

比如第一层是首字母，第二层是尾字母，第三层是单词长度-2这样。根据hash function效果不同，通常这样能省更多的内存，不过也更容易写出bug就是了

我有点看不懂你们想怎么写。这题不是很简单。
List<String> find(String s, String[] L) {
        List<String> res = new ArrayList<>();
        for ( String l : L) {
                if (isValid(s, l)) {
                        res.add(l);
                }
        }
       
        return res;
}
boolean isValid (String s, String l) {
    if (l.length() < 2) {
            return false;
        }
        String convert = s.charAt(0) + String.valueOf(s.length() - 2) + s.charAt(s.length() - 1);
        return s.equals(convert);
}

请问lz这题用tree的思路是什么呀。没想明白

m4reiiy 发表于 2015-4-11 03:39
比如第一层是首字母，第二层是尾字母，第三层是单词长度-2这样。根据hash function效果不同，通常这样能 ...

好厉害！这个方法很聪明。有人说他follow up了一下把abbr升级了一下，比如localise  -》 l2al1s1如何去找。这样出了trie 还有其他办法么？

mm豆 发表于 2015-4-10 14:52
好厉害！这个方法很聪明。有人说他follow up了一下把abbr升级了一下，比如localise  -》 l2al1s1如何去找 ...

如果目标是解决这个扩展问题的话应该trie比较万能，直接在trie上BFS+pruning应该就够快了。

m4reiiy 发表于 2015-4-12 03:47
如果目标是解决这个扩展问题的话应该trie比较万能，直接在trie上BFS+pruning应该就够快了。

明白了，谢谢～～～