国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LeetCode] Palindrome Pairs

DangoSky / 2244人閱讀

摘要:和的區(qū)別是,所以對于,效率更高不允許作為鍵值,而允許一個鍵和無限個值有一個,叫,便于查詢可預(yù)測的迭代順序。這道題依然選擇的話

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的區(qū)別:

HashTable是synchronized,所以對于non-threaded applications,HashMap效率更高;
HashTable不允許null作為鍵值,而HashMap允許一個null鍵和無限個null值;
HashMap有一個subclass,叫LinkedHashMap,便于查詢可預(yù)測的迭代順序。

為什么Trie比HashMap效率更高

Trie可以在O(L)(L為word.length)的時間復(fù)雜度下進(jìn)行插入和查詢操作;
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           
               
                                           
                       
                 

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/66011.html

相關(guān)文章

  • LeetCode 336. Palindrome Pairs

    摘要:描述給定一組唯一的單詞,找出所有不同的索引對,使得列表中的兩個單詞,,可拼接成回文串。遍歷每一個單詞,對每一個單詞進(jìn)行切片,組成和。 Description Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenatio...

    TigerChain 評論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 評論0 收藏0
  • Palindrome Pairs & Shortest Palindrome

    摘要:部分是回文的,在里面找是否有的。這里的范圍是,最小是,因為要保證是兩個單詞,最大是,這時候要找出另一個和他相反的串。判斷為回文,可以直接暴力,每個都判斷一次。兩個方向都找一遍就可能出現(xiàn)重復(fù)的情況,注意避免重復(fù)。例如,結(jié)果應(yīng)該是。 Palindrome Pairs 鏈接:https://leetcode.com/problems... 這道題沒想出來思路,參考了這個博客的內(nèi)容:http:...

    CNZPH 評論0 收藏0
  • 336. Palindrome Pairs

    摘要:容易出的兩個地方以為例。這兩個互為的在尾部加上也就是在頭部加上所以后部分不能為空,否則就和頭部為空的情況重復(fù)了。空間復(fù)雜度因為用了額外的來儲存,需要空間。時間復(fù)雜度每個分為兩個部分,調(diào)用前后兩部分總長度為所以每次調(diào)用為一共次。 Given a list of unique words, find all pairs of distinct indices (i, j) in the g...

    Guakin_Huang 評論0 收藏0
  • leetcode 部分解答索引(持續(xù)更新~)

    摘要:前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。 順序整理 1~50 1...

    leo108 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<