336. 回文对(前缀树)

2024-02-17 11:48
文章标签 回文 前缀 336

本文主要是介绍336. 回文对(前缀树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

给定一组 互不相同 的单词, 找出所有不同 的索引对(i, j),使得列表中的两个单词, words[i] + words[j] ,可拼接成回文串。

示例 1:输入:["abcd","dcba","lls","s","sssll"]
输出:[[0,1],[1,0],[3,2],[2,4]] 
解释:可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2:输入:["bat","tab","cat"]
输出:[[0,1],[1,0]] 
解释:可拼接成的回文串为 ["battab","tabbat"]来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/palindrome-pairs
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
Solution 1 暴力枚举
class Solution:def palindromePairs(self, words: List[str]) -> List[List[int]]:def check(s):n = len(s)left, right = 0, n - 1while left < right:if s[left] != s[right]:return Falseleft, right = left + 1, right - 1return Trueans = []for i in range(len(words)):for j in range(i+1, len(words)):if check(words[i]+words[j]):ans.append([i, j])if check(words[j]+words[i]):ans.append([j, i])return ans
Solution 2 前缀树
class Node:def __init__(self):self.ch = [0] * 26self.flag = -1class Solution:def palindromePairs(self, words: List[str]) -> List[List[int]]:tree = [Node()]def insert(s: str, index: int):length = len(s)add = 0for i in range(length):x = ord(s[i]) - ord("a")if tree[add].ch[x] == 0:tree.append(Node())tree[add].ch[x] = len(tree) - 1add = tree[add].ch[x]tree[add].flag = indexdef findWord(s: str, left: int, right: int) -> int:add = 0for i in range(right, left - 1, -1):x = ord(s[i]) - ord("a")if tree[add].ch[x] == 0:return -1add = tree[add].ch[x]return tree[add].flagdef isPalindrome(s: str, left: int, right: int) -> bool:length = right - left + 1return length < 0 or all(s[left + i] == s[right - i] for i in range(length // 2))n = len(words)for i, word in enumerate(words):insert(word, i)ret = list()for i, word in enumerate(words):m = len(word)for j in range(m + 1):if isPalindrome(word, j, m - 1):leftId = findWord(word, 0, j - 1)if leftId != -1 and leftId != i:ret.append([i, leftId])if j and isPalindrome(word, 0, j - 1):rightId = findWord(word, j, m - 1)if rightId != -1 and rightId != i:ret.append([rightId, i])return ret作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/palindrome-pairs/solution/hui-wen-dui-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

这篇关于336. 回文对(前缀树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/717657

相关文章

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

【LeetCode热题100】前缀和

这篇博客共记录了8道前缀和算法相关的题目,分别是:【模版】前缀和、【模版】二维前缀和、寻找数组的中心下标、除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和。 #include <iostream>#include <vector>using namespace std;int main() {//1. 读取数据int n = 0, q = 0;ci

前缀和 — 利用前缀信息解决子数组问题

【前缀和的核心思想是预先处理数组来快速计算任意子数组的和,基本上用于数组和序列问题。】 前缀和算法具体步骤 构造前缀和数组: 给定一个数组nums,其前缀和数组prex定义为prex[i]表示为数组nums从起始位置到第i个位置的元素累加和。构建前缀和公式: p r e x [ i ] = n u m s [ i ] ( i = = 0 ) p r e x [ i ] = p r e x

每日一题~cf 970 div3 (A思维,B小模拟,C二分,D排列数建图成环,E 26个字母暴力+前缀和,F 逆元,G 数论gcd )

A 题意: 有 a 个1 ,b 个2.问是否能将这些数划分为两个数值相等的集合。 输出 YES 或者 NO —————— 问题等价于 将数组 分成两个数值相同的数组。所以sum 应该是偶数。也就是说 1 的个数是偶数。在i1的个数是偶数的情况下,将 2 分成两份,如果2 的个数是偶数,OK。如果是奇数那么需要1来补齐,如果1 的个数大于等于2那么可以补齐。(1 的个数是偶数,需要2个1来补齐,剩下

NYOJ 37 回文字符串(记忆化搜索)

OJ题目 : 戳这里~~ 描述 所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的,比如"aba"。当然,我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你,给你一个字符串,可在任意位置添加字符,最少再添加几个字符,可以使这个字符串成为回文字符串。 输入 第一行给出整数N(0<N<100) 接下来的N行,每行一个字符串,每个字符串长度不超过1000.

【数据结构-二维前缀和】力扣1504. 统计全 1 子矩形

给你一个 m x n 的二进制矩阵 mat ,请你返回有多少个 子矩形 的元素全部都是 1 。 示例 1: 输入:mat = [[1,0,1],[1,1,0],[1,1,0]] 输出:13 解释: 有 6 个 1x1 的矩形。 有 2 个 1x2 的矩形。 有 3 个 2x1 的矩形。 有 1 个 2x2 的矩形。 有 1 个 3x1 的矩形。 矩形数目总共 = 6 + 2 + 3 + 1 +

leetcode: 5. 最长回文子串

5. 最长回文子串 题目链接https://leetcode.cn/problems/longest-palindromic-substring/ 题目描述 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2:

java常用算法之最长回文子串(Longest Palindromic Substring)

方法一:时间复杂度为O(n^3) public static String longestPalindrome1(String s) {int maxPalinLength = 0;String longestPalindrome = null;int length = s.length();// check all possible sub stringsfor (int i = 0; i

Python高效实现Trie(前缀树)及其插入和查找操作

Python高效实现Trie(前缀树)及其插入和查找操作 在Python面试中,考官通常会关注候选人的编程能力、问题解决能力以及对Python语言特性的理解。Trie(前缀树)是一种高效的数据结构,广泛应用于字符串处理、自动补全、拼写检查等场景。本文将详细介绍如何实现一个Trie,并提供插入和查找操作,确保代码实用性强,条理清晰,操作性强。 1. 引言 Trie(前缀树)是一种树形数据结构,