LeetCode 336. Palindrome Pairs

本文涉及的产品
模型训练 PAI-DLC,5000CU*H 3个月
模型在线服务 PAI-EAS,A10/V100等 500元 1个月
交互式建模 PAI-DSW,5000CU*H 3个月
简介: 给定一组唯一的单词, 找出所有不同 的索引对(i, j),使得列表中的两个单词, words[i] + words[j] ,可拼接成回文串。

v2-431709d2803f668abd7256361c1132f4_1440w.jpg

Description



Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.


Example 1:

Input: ["abcd","dcba","lls","s","sssll"]

Output: [[0,1],[1,0],[3,2],[2,4]]

Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]


Example 2:

Input: ["bat","tab","cat"]

Output: [[0,1],[1,0]]

Explanation: The palindromes are ["battab","tabbat"]


描述



给定一组唯一的单词, 找出所有不同 的索引对(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"]


思路



  • 构建字典,字典的键为单词,值为单词的索引。
  • 遍历每一个单词,对每一个单词进行切片,组成 prefix 和 subfix。
  • 如果 prefix 本身是回文字符串,我们检查 subfix 的反转是否在字典中,如果在,说明可以构成一个满足题意的回文字符串,我们将该键的值,当前单词的索引构成一个组合(注意顺序)。
  • 如果 subfix 是一回文字符串,我们检查 prefix 的反抓是否在字典中,如果在,说明可以构成一个满足题意的回文字符串,我们将当前单词的索引,该键的值构成一个组个(注意顺序)
  • 注意在检查回文字符串的时候,注意重复。


# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-04-06 12:11:30
# @Last Modified by:   何睿
# @Last Modified time: 2019-04-07 10:20:01
class Solution:
    def palindromePairs(self, words: [str]) -> [[int]]:
        # 结果数组
        result = []
        # 字典,用于获取索引
        worddict = {word: i for i, word in enumerate(words)}
        for i, word in enumerate(words):
            count = len(word)
            for j in range(count + 1):
                # 获取字段的前半部分,后半部分
                prefix, subfix = word[:j], word[j:]
                # 前半部分的反转,后半部分的反转
                reprefix, resubfix = prefix[::-1], subfix[::-1]
                # 如果前半部分是 palindrome 并且后半部分的反转在字典中
                if prefix == reprefix and resubfix in worddict:
                    m = worddict[resubfix]
                    # 不能取到字符本身
                    if m != i: result.append([m, i])
                # 如果后半部分是回文字符串,并且前半部分的逆序在字典中
                if j != count and subfix == resubfix and reprefix in worddict:
                    result.append([i, worddict[reprefix]])
        return result

源代码文件在 这里


相关实践学习
使用PAI-EAS一键部署ChatGLM及LangChain应用
本场景中主要介绍如何使用模型在线服务(PAI-EAS)部署ChatGLM的AI-Web应用以及启动WebUI进行模型推理,并通过LangChain集成自己的业务数据。
机器学习概览及常见算法
机器学习(Machine Learning, ML)是人工智能的核心,专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能,它是使计算机具有智能的根本途径,其应用遍及人工智能的各个领域。 本课程将带你入门机器学习,掌握机器学习的概念和常用的算法。
目录
相关文章
|
11月前
Leetcode 24.Swap Nodes in Pairs
 给你一个链表,交换相邻两个节点,例如给你 1->2->3->4,输出2->1->4->3。   我代码里在head之前新增了一个节点newhead,其实是为了少写一些判断head的代码。
35 0
LeetCode 409. Longest Palindrome
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。 在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
70 0
LeetCode 409. Longest Palindrome
|
算法 索引
LeetCode 214. Shortest Palindrome
给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
80 0
LeetCode 214. Shortest Palindrome
|
canal
LeetCode 125. Valid Palindrome
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
87 0
LeetCode 125. Valid Palindrome
LeetCode 234. 回文链表 Palindrome Linked List
LeetCode 234. 回文链表 Palindrome Linked List
Leetcode-Easy 234. Palindrome Linked List
Leetcode-Easy 234. Palindrome Linked List
54 0
Leetcode-Easy 234. Palindrome Linked List
【LeetCode】Palindrome Pairs(336)
  Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a   palindrome.
108 0
LeetCode之Palindrome Number(回文数)
LeetCode之Palindrome Number(回文数)
70 0
|
Java Python
LeetCode 234:回文链表 Palindrome Linked List
​请判断一个链表是否为回文链表。 Given a singly linked list, determine if it is a palindrome. 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题? Follow up:Could you do it in O(n) time and O(1) space? 解题思路: 首先是寻找链表中间节点,这个可以用快慢指针来解决,快指针速度为2,慢指针速度为1,快指针遍历完链表时,慢指针刚好走到中间节点(相对)。
686 0
|
10天前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行

热门文章

最新文章