摘要:和的區(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的話
public V getOrDefault(Object key,V defaultValue)
Data Type | Parameter | Description |
---|---|---|
Object Key | key | the key whose associated value is to be returned |
V | defaultValue | the default mapping of the key |
The getOrDefault() method returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key.
@SafeVarargs public staticList asList(T… a)
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 |
The asList() method returns a list view of the specified array.
Solution Using Triepublic class Solution { class TrieNode { TrieNode[] next; int index; ListHashMap methodlist; 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; } }
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
摘要:描述給定一組唯一的單詞,找出所有不同的索引對,使得列表中的兩個單詞,,可拼接成回文串。遍歷每一個單詞,對每一個單詞進(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...
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...
摘要:部分是回文的,在里面找是否有的。這里的范圍是,最小是,因為要保證是兩個單詞,最大是,這時候要找出另一個和他相反的串。判斷為回文,可以直接暴力,每個都判斷一次。兩個方向都找一遍就可能出現(xiàn)重復(fù)的情況,注意避免重復(fù)。例如,結(jié)果應(yīng)該是。 Palindrome Pairs 鏈接:https://leetcode.com/problems... 這道題沒想出來思路,參考了這個博客的內(nèi)容:http:...
摘要:容易出的兩個地方以為例。這兩個互為的在尾部加上也就是在頭部加上所以后部分不能為空,否則就和頭部為空的情況重復(fù)了。空間復(fù)雜度因為用了額外的來儲存,需要空間。時間復(fù)雜度每個分為兩個部分,調(diào)用前后兩部分總長度為所以每次調(diào)用為一共次。 Given a list of unique words, find all pairs of distinct indices (i, j) in the g...
摘要:前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。 順序整理 1~50 1...
閱讀 1002·2021-09-30 09:58
閱讀 2829·2021-09-09 11:55
閱讀 2001·2021-09-01 11:41
閱讀 991·2019-08-30 15:55
閱讀 3350·2019-08-30 12:50
閱讀 3495·2019-08-29 18:37
閱讀 3295·2019-08-29 16:37
閱讀 2011·2019-08-29 13:00