标签: Hash

评分 5.00, 满分 5 星
1 票

使用字符哈希卡着时间过的,时间复杂度是max(O(K), O(n^2)),K是所有字符串的长度和,n是字符串的个数。处理出每个字符串的正向和逆向哈希值,拼接的时候相当分配一个幂指数的权重,若正、逆哈希值相等则判相等。因此可以O(n^2)枚举,O(1)判断。tag中提到了Trie,改天会写一个Trie的版本。

Comments Off on [LeetCode]Palindrome Pairs

评分 0, 满分 5 星
0 票

反转一下,然后分别做一遍正向和逆向的哈希,哈希值相同就是回文。

Comments Off on [LeetCode]Palindrome Linked List

评分 0, 满分 5 星
0 票

每次在字符串首部添加的字符总是会优先和字符串尾部的字符匹配,因此不难发现,只要找到从当前给定字符串最左字符开始的连续最长的回文串,就能得到最少需要添加的字符。这时可以对原字符串,正向哈希一遍,逆向哈希一遍,然后枚举一遍长度即可。时间复杂度O(n)。

Comments Off on [LeetCode]Shortest Palindrome

评分 0, 满分 5 星
0 票

字符串哈希,借助set判断答案及重复。(马上除夕夜了,祈求新的一年一切都好,Happy new year)