摘要:容易出的兩個地方以為例。這兩個互為的在尾部加上也就是在頭部加上所以后部分不能為空,否則就和頭部為空的情況重復(fù)了。空間復(fù)雜度因為用了額外的來儲存,需要空間。時間復(fù)雜度每個分為兩個部分,調(diào)用前后兩部分總長度為所以每次調(diào)用為一共次。
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. Given words = ["abcd", "dcba", "lls", "s", "sssll"] Return [[0, 1], [1, 0], [3, 2], [2, 4]] The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]
暴力解法就不贅述了,找出所有pairs,逐一驗證isPalindrome. 時間復(fù)雜度O(N^2*k). palindrome最大的特性就是對稱,按長度的奇偶可以分為str,char,reverse(str)還有 str,reverse(str)型。 我們有一個str,在i這個位置進行切分,得到的前半部分是一個palindrome. 比如"lls", 變成"ll", "s". 已知"ll"是palindrome,我們只需要知道reverse("s") 放到前邊就可以了。 reverse("s")"ll""s", 即reverse(str) PalindromeSubString str的類型。 還有一種就是后半部分是palindrome, 我們找到前半部分的reverse,拼到后面。["abcdc", "ba"]。 "cdc"是palindrome, reverse(ab) 就是 "ba", 我們有這樣的string出現(xiàn)過。 代碼細(xì)節(jié)就是有一個isPalindrome的helper function。 一個hashmap存入所有paris加速查詢。 容易出bug的兩個地方, 以["abcd", "dcba", "lls", "s", "sssll"]為例。 1. 如果一個str本身就是panlindrome,reverse就是本身,一定在hashmap里,去重的方法就是判斷map.get(reverse(str)) != i. [[1,0],[0,1],[3,2],[3,3],[2,4]] 2. 我們在切割str的時候,j ==0時str變成""和"str", j == str.length()的時候str變成"str"和""。 "abcd", "dcba"這兩個互為reverse的string, 在"abcd"尾部加上"dcba"也就是在"dcba"頭部加上"abcd". 所以后部分不能為空,否則就和頭部為空的情況重復(fù)了。 [[1,0],[0,1],[0,1],[1,0],[3,2],[2,4]] 空間復(fù)雜度因為用了額外的hashmap來儲存,需要O(N)空間。 時間復(fù)雜度每個str分為兩個部分,調(diào)用isPalindrome,前后兩部分總長度為k. 所以每次調(diào)用為O(k)一共(k+1)次。 然后一共有N個str, 總共時間復(fù)雜度為O(N*k^2).
public class Solution { public List> palindromePairs(String[] words) { List
> res = new ArrayList
>(); if(words == null || words.length == 0) return res; HashMap
map = new HashMap<>(); for(int i = 0; i < words.length; i++) map.put(words[i], i); for(int i = 0; i < words.length; i++){ for(int j = 0; j <= words[i].length(); j++){ String str1 = words[i].substring(0, j); String str2 = words[i].substring(j); if(isPalindrome(str1)){ String str2rvs = new StringBuilder(str2).reverse().toString(); if(map.containsKey(str2rvs) && map.get(str2rvs) != i){ List list = new ArrayList (); list.add(map.get(str2rvs)); list.add(i); res.add(list); } } if(isPalindrome(str2) && str2.length() != 0){ String str1rvs = new StringBuilder(str1).reverse().toString(); if(map.containsKey(str1rvs) && map.get(str1rvs) != i){ List list = new ArrayList (); list.add(i); list.add(map.get(str1rvs)); res.add(list); } } } } return res; } public boolean isPalindrome(String s){ int left = 0, right = s.length() - 1; while(left < right){ if(s.charAt(left++) != s.charAt(right--)) return false; } return true; } }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/66908.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...
摘要:部分是回文的,在里面找是否有的。這里的范圍是,最小是,因為要保證是兩個單詞,最大是,這時候要找出另一個和他相反的串。判斷為回文,可以直接暴力,每個都判斷一次。兩個方向都找一遍就可能出現(xiàn)重復(fù)的情況,注意避免重復(fù)。例如,結(jié)果應(yīng)該是。 Palindrome Pairs 鏈接:https://leetcode.com/problems... 這道題沒想出來思路,參考了這個博客的內(nèi)容:http:...
摘要:和的區(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...
摘要:前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。 順序整理 1~50 1...
閱讀 1700·2021-11-02 14:47
閱讀 3648·2019-08-30 15:44
閱讀 1334·2019-08-29 16:42
閱讀 1731·2019-08-26 13:53
閱讀 935·2019-08-26 10:41
閱讀 3458·2019-08-23 17:10
閱讀 597·2019-08-23 14:24
閱讀 1717·2019-08-23 11:59