336. Palindrome Pairs

Guakin_Huang 发布于2019-08-14 17:57 / 1686人阅读

摘要：容易出的两个地方以为例。这两个互为的在尾部加上也就是在头部加上所以后部分不能为空，否则就和头部为空的情况重复了。空间复杂度因为用了额外的来储存，需要空间。时间复杂度每个分为两个部分，调用前后两部分总长度为所以每次调用为一共次。

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.

Given words = ["abcd", "dcba", "lls", "s", "sssll"]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]

暴力解法就不赘述了，找出所有pairs，逐一验证isPalindrome. 时间复杂度O(N^2*k).
palindrome最大的特性就是对称，按长度的奇偶可以分为str,char,reverse(str)还有 str,reverse(str)型。
我们有一个str,在i这个位置进行切分，得到的前半部分是一个palindrome. 比如"lls", 变成"ll", "s".
已知"ll"是palindrome，我们只需要知道reverse("s") 放到前边就可以了。
reverse("s")"ll""s", 即reverse(str) PalindromeSubString str的类型。

还有一种就是后半部分是palindrome, 我们找到前半部分的reverse,拼到后面。["abcdc", "ba"]。
"cdc"是palindrome, reverse(ab) 就是 "ba", 我们有这样的string出现过。

代码细节就是有一个isPalindrome的helper function。 一个hashmap存入所有 paris加速查询。
容易出bug的两个地方, 以["abcd", "dcba", "lls", "s", "sssll"]为例。
1. 如果一个str本身就是panlindrome，reverse就是本身，一定在hashmap里，去重的方法就是判断map.get(reverse(str)) != i.
   [[1,0],[0,1],[3,2],[3,3],[2,4]]
2. 我们在切割str的时候，j ==0时str变成""和"str",  j == str.length()的时候str变成"str"和""。
   "abcd", "dcba"这两个互为reverse的string, 在"abcd"尾部加上"dcba"也就是在"dcba"头部加上"abcd".
   所以后部分不能为空，否则就和头部为空的情况重复了。
   [[1,0],[0,1],[0,1],[1,0],[3,2],[2,4]]

空间复杂度因为用了额外的hashmap来储存，需要O(N)空间。
时间复杂度每个str分为两个部分，调用isPalindrome,前后两部分总长度为k. 所以每次调用为O(k)一共(k+1)次。
然后一共有N个str, 总共时间复杂度为O(N*k^2).

public class Solution {
    public List> palindromePairs(String[] words) {
        List> res = new ArrayList>();
        if(words == null || words.length == 0) return res;
        HashMap map = new HashMap<>();
        for(int i = 0; i < words.length; i++) map.put(words[i], i);
        
        for(int i = 0; i < words.length; i++){
            for(int j = 0; j <= words[i].length(); j++){
                String str1 = words[i].substring(0, j);
                String str2 = words[i].substring(j);
                
                if(isPalindrome(str1)){
                    String str2rvs = new StringBuilder(str2).reverse().toString();
                    if(map.containsKey(str2rvs) && map.get(str2rvs) != i){
                        List list = new ArrayList();
                        list.add(map.get(str2rvs));
                        list.add(i);
                        res.add(list);
                    }
                } 
                if(isPalindrome(str2) && str2.length() != 0){
                    String str1rvs = new StringBuilder(str1).reverse().toString();
                    if(map.containsKey(str1rvs) && map.get(str1rvs) != i){
                        List list = new ArrayList();
                        list.add(i);
                        list.add(map.get(str1rvs));
                        res.add(list);
                    }
                }
                
            }
        }
        return res;
    }
    
    public boolean isPalindrome(String s){
        int left = 0, right = s.length() - 1;
        while(left < right){
            if(s.charAt(left++) != s.charAt(right--)) return false;
        }
        return true;
    }
}

GPU云服务器云服务器 pairs palindrome 云主机336 java是什么336

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66908.html

LeetCode 336. Palindrome Pairs

摘要：描述给定一组唯一的单词，找出所有不同的索引对，使得列表中的两个单词，，可拼接成回文串。遍历每一个单词，对每一个单词进行切片，组成和。 Description Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenatio...

TigerChain 2019-07-31 10:16 评论0 收藏0
[LeetCode] 336. Palindrome Pairs

Problem 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: Inpu...

lentoo 2019-08-16 13:45 评论0 收藏0
Palindrome Pairs & Shortest Palindrome

摘要：部分是回文的，在里面找是否有的。这里的范围是，最小是，因为要保证是两个单词，最大是，这时候要找出另一个和他相反的串。判断为回文，可以直接暴力，每个都判断一次。两个方向都找一遍就可能出现重复的情况，注意避免重复。例如，结果应该是。 Palindrome Pairs 链接：https://leetcode.com/problems... 这道题没想出来思路，参考了这个博客的内容：http:...

CNZPH 2019-08-14 17:20 评论0 收藏0
[LeetCode] Palindrome Pairs

摘要：和的区别是，所以对于，效率更高不允许作为键值，而允许一个键和无限个值有一个，叫，便于查询可预测的迭代顺序。这道题依然选择的话 Problem Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the...

DangoSky 2019-08-14 15:47 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0