[LeetCode] Palindrome Pairs

DangoSky 发布于2019-08-14 15:47 / 2102人阅读

摘要：和的区别是，所以对于，效率更高不允许作为键值，而允许一个键和无限个值有一个，叫，便于查询可预测的迭代顺序。这道题依然选择的话

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:

Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]

Example 2:

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

Note

HashMap和HashTable的区别：

HashTable是synchronized，所以对于non-threaded applications，HashMap效率更高；
HashTable不允许null作为键值，而HashMap允许一个null键和无限个null值；
HashMap有一个subclass，叫LinkedHashMap，便于查询可预测的迭代顺序。

为什么Trie比HashMap效率更高

Trie可以在O(L)（L为word.length）的时间复杂度下进行插入和查询操作；
HashMap和HashTable只能找到完全匹配的词组，而Trie可以找到有相同前缀的、有不同字符的、有缺失字符的词组。

这道题依然选择HashMap的话

1. map.getOrDefault(str, i)

Method Syntax

public V getOrDefault(Object key,V defaultValue)

Method Argument

Data Type	Parameter	Description
Object Key	key	the key whose associated value is to be returned
V	defaultValue	the default mapping of the key

Method Returns

The getOrDefault() method returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key.

2. Arrays.asList(i, j)

Method Syntax

@SafeVarargs
public static  List asList(T… a)

Method Argument

Data Type	Parameter	Description
T	a	T – the class of the objects in the array
		a – the array by which the list will be backed

Method Returns

The asList() method returns a list view of the specified array.

Solution Using Trie

public class Solution {
    class TrieNode {
        TrieNode[] next;
        int index;
        List list;
        TrieNode() {
            next = new TrieNode[26];
            index = -1;
            list = new ArrayList<>();
        }
    }
    public List> palindromePairs(String[] words) {
        List> res = new ArrayList<>();
        TrieNode root = new TrieNode();
        for (int i = 0; i < words.length; i++) addWord(root, words[i], i);
        for (int i = 0; i < words.length; i++) search(words, i, root, res);
        return res;
    }
    private void addWord(TrieNode root, String word, int index) {
        for (int i = word.length() - 1; i >= 0; i--) {
            if (root.next[word.charAt(i) - "a"] == null) root.next[word.charAt(i) - "a"] = new TrieNode();
            if (isPalindrome(word, 0, i)) root.list.add(index);
            root = root.next[word.charAt(i) - "a"];
        }
        root.list.add(index);
        root.index = index;
    }
    private void search(String[] words, int i, TrieNode root, List> list) {
        for (int j = 0; j < words[i].length(); j++) {   
            if (root.index >= 0 && root.index != i && isPalindrome(words[i], j, words[i].length() - 1)) list.add(Arrays.asList(i, root.index));
            root = root.next[words[i].charAt(j) - "a"];
            if (root == null) return;
        }
        for (int j : root.list) {
            if (i == j) continue;
            list.add(Arrays.asList(i, j));
        }
    }
    private boolean isPalindrome(String word, int i, int j) {
        while (i < j) {
            if (word.charAt(i++) != word.charAt(j--)) return false;
        }
        return true;
    }
}

HashMap method

public class Solution {
    public List> palindromePairs(String[] words) {
        List> ret = new ArrayList<>(); 
        if (words == null || words.length < 2) return ret;
        Map map = new HashMap<>();
        for (int i=0; i

云服务器海外云主机 pairs palindrome LeetCode LeetCode_String

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

转载请注明本文地址：https://www.ucloud.cn/yun/66011.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
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 部分解答索引（持续更新～）

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

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