摘要:和的區別是,所以對于,效率更高不允許作為鍵值,而允許一個鍵和無限個值有一個,叫,便于查詢可預測的迭代順序。這道題依然選擇的話
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的話
</>復制代碼
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 static List 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 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
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/66011.html
摘要:描述給定一組唯一的單詞,找出所有不同的索引對,使得列表中的兩個單詞,,可拼接成回文串。遍歷每一個單詞,對每一個單詞進行切片,組成和。 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...
摘要:部分是回文的,在里面找是否有的。這里的范圍是,最小是,因為要保證是兩個單詞,最大是,這時候要找出另一個和他相反的串。判斷為回文,可以直接暴力,每個都判斷一次。兩個方向都找一遍就可能出現重復的情況,注意避免重復。例如,結果應該是。 Palindrome Pairs 鏈接:https://leetcode.com/problems... 這道題沒想出來思路,參考了這個博客的內容:http:...
摘要:容易出的兩個地方以為例。這兩個互為的在尾部加上也就是在頭部加上所以后部分不能為空,否則就和頭部為空的情況重復了??臻g復雜度因為用了額外的來儲存,需要空間。時間復雜度每個分為兩個部分,調用前后兩部分總長度為所以每次調用為一共次。 Given a list of unique words, find all pairs of distinct indices (i, j) in the g...
摘要:前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的??赡艽蠹铱粗卜浅2环奖恪K栽谶@里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫~現在翻起來覺得蠻亂的??赡艽蠹铱粗卜浅2环奖?。所以在這里做個索引嘻嘻。 順序整理 1~50 1...
閱讀 1015·2021-09-30 09:58
閱讀 2848·2021-09-09 11:55
閱讀 2010·2021-09-01 11:41
閱讀 1004·2019-08-30 15:55
閱讀 3363·2019-08-30 12:50
閱讀 3508·2019-08-29 18:37
閱讀 3310·2019-08-29 16:37
閱讀 2023·2019-08-29 13:00