成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

336. Palindrome Pairs

Guakin_Huang / 1827人閱讀

摘要：容易出的兩個(gè)地方以為例。這兩個(gè)互為的在尾部加上也就是在頭部加上所以后部分不能為空，否則就和頭部為空的情況重復(fù)了。空間復(fù)雜度因?yàn)橛昧祟~外的來儲(chǔ)存，需要空間。時(shí)間復(fù)雜度每個(gè)分為兩個(gè)部分，調(diào)用前后兩部分總長(zhǎng)度為所以每次調(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，逐一驗(yàn)證isPalindrome. 時(shí)間復(fù)雜度O(N^2*k).
palindrome最大的特性就是對(duì)稱，按長(zhǎng)度的奇偶可以分為str,char,reverse(str)還有 str,reverse(str)型。
我們有一個(gè)str,在i這個(gè)位置進(jìn)行切分，得到的前半部分是一個(gè)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é)就是有一個(gè)isPalindrome的helper function。 一個(gè)hashmap存入所有 paris加速查詢。
容易出bug的兩個(gè)地方, 以["abcd", "dcba", "lls", "s", "sssll"]為例。
1. 如果一個(gè)str本身就是panlindrome，reverse就是本身，一定在hashmap里，去重的方法就是判斷map.get(reverse(str)) != i.
   [[1,0],[0,1],[3,2],[3,3],[2,4]]
2. 我們?cè)谇懈顂tr的時(shí)候，j ==0時(shí)str變成""和"str",  j == str.length()的時(shí)候str變成"str"和""。
   "abcd", "dcba"這兩個(gè)互為reverse的string, 在"abcd"尾部加上"dcba"也就是在"dcba"頭部加上"abcd".
   所以后部分不能為空，否則就和頭部為空的情況重復(fù)了。
   [[1,0],[0,1],[0,1],[1,0],[3,2],[2,4]]

空間復(fù)雜度因?yàn)橛昧祟~外的hashmap來儲(chǔ)存，需要O(N)空間。
時(shí)間復(fù)雜度每個(gè)str分為兩個(gè)部分，調(diào)用isPalindrome,前后兩部分總長(zhǎng)度為k. 所以每次調(diào)用為O(k)一共(k+1)次。
然后一共有N個(gè)str, 總共時(shí)間復(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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66908.html

相關(guān)文章

  • LeetCode 336. Palindrome Pairs

    摘要：描述給定一組唯一的單詞，找出所有不同的索引對(duì)，使得列表中的兩個(gè)單詞，，可拼接成回文串。遍歷每一個(gè)單詞，對(duì)每一個(gè)單詞進(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 評(píng)論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 評(píng)論0 收藏0

  • Palindrome Pairs & Shortest Palindrome

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

    CNZPH 評(píng)論0 收藏0

  • [LeetCode] Palindrome Pairs

    摘要：和的區(qū)別是，所以對(duì)于，效率更高不允許作為鍵值，而允許一個(gè)鍵和無(wú)限個(gè)值有一個(gè)，叫，便于查詢可預(yù)測(cè)的迭代順序。這道題依然選擇的話 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...

    DangoSky 評(píng)論0 收藏0

  • leetcode 部分解答索引（持續(xù)更新～）

    摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...

    leo108 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<