[LeetCode] 336. Palindrome Pairs

lentoo 发布于2019-08-16 13:45 / 1849人阅读

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:

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"]

Solution

class Solution {
    public List> palindromePairs(String[] words) {
        List> res = new ArrayList<>();
        if (words == null || words.length == 0) return res;
        Map map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            map.put(words[i], i);
        }
        
        if (map.containsKey("")) {
            int blankIndex = map.get("");
            for (int i = 0; i < words.length; i++) {
                if (isPalindrome(words[i]) && i != blankIndex) {
                    res.add(Arrays.asList(blankIndex, i));
                    res.add(Arrays.asList(i, blankIndex));
                }
            }
        }
        
        for (int i = 0; i < words.length; i++) {
            String reversed = new StringBuilder(words[i]).reverse().toString();
            if (map.containsKey(reversed)) {
                int index = map.get(reversed);
                if (index != i) {
                    res.add(Arrays.asList(i, index));
                }
            }
        }
        
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            for (int j = 1; j < word.length(); j++) {
                if (isPalindrome(word.substring(0, j))) {
                    String reversed = new StringBuilder(word.substring(j)).reverse().toString();
                    if (map.containsKey(reversed)) {
                        int index = map.get(reversed);
                        if (index != i) {
                            res.add(Arrays.asList(index, i));
                        }
                    }
                }
                if (isPalindrome(word.substring(j))) {
                    String reversed = new StringBuilder(word.substring(0, j)).reverse().toString();
                    if (map.containsKey(reversed)) {
                        int index = map.get(reversed);
                        if (index != i) {
                            res.add(Arrays.asList(i, index));
                        }
                    }
                }
            }
        }
        
        return res;
    }
    
    private boolean isPalindrome(String word) {
        if (word == null || word.length() <= 1) return true;
        int i = 0, j = word.length()-1;
        while (i < j) {
            if (word.charAt(i) != word.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}

云服务器 GPU云服务器 pairs palindrome 云主机336 LeetCode

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

转载请注明本文地址：https://www.ucloud.cn/yun/72276.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
336. Palindrome Pairs

摘要：容易出的两个地方以为例。这两个互为的在尾部加上也就是在头部加上所以后部分不能为空，否则就和头部为空的情况重复了。空间复杂度因为用了额外的来储存，需要空间。时间复杂度每个分为两个部分，调用前后两部分总长度为所以每次调用为一共次。 Given a list of unique words, find all pairs of distinct indices (i, j) in the g...

Guakin_Huang 2019-08-14 17:57 评论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
Palindrome Pairs & Shortest Palindrome

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

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

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

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