Citadel 2019 summer SDE Intern OA

wy16119 发表于 2018-11-11 11:59
请问楼主 第二题马拉车是什么解法呀？

manacher算法，用于处理回文字串，O(1)时间

LaSeineFirenze 发表于 2018-11-11 14:09
manacher算法，用于处理回文字串，O(1)时间

错了错了，O(n)时间

LaSeineFirenze 发表于 2018-11-11 14:08
这是个图不是树，所以会有一个节点多个root的情况。从入度为0的点开始做BFS就可以了

那楼主你是用什么结构存这个图的啊 能详细说下吗 另外第二题我是用O(n^2)做的  你说的那个O(n)方法能介绍下吗 给你加米了

wy16119 发表于 2018-11-12 03:13
那楼主你是用什么结构存这个图的啊 能详细说下吗 另外第二题我是用O(n^2)做的  你说的那个O(n)方法能介绍 ...

我用的是邻接表，先用一个hashmap存下所有的字符串和index，然后对于每个字符串，分别删掉每个字符，看剩下的字符串是否在hashmap里。
第二题搜manacher palindromic substring，是个比较巧的方法，要统计个数的话就用hashset保存出现过的子串。