摘要:暴力算法就是找到所有每個都進行的檢查。時間復雜度是個調用平均時長為這里唯一確定用的是頭尾表示。因為的對稱性,我們可以從中間出發向兩邊延展,找到最長的分為兩種基本情況。奇數長度出發點一致,都為偶數長度出發點為相鄰的點,和結束是
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
暴力算法就是找到所有substring, 每個都進行isPalindrome的檢查。時間復雜度是O(N^3). N^2個substring, 調用isPalindrome平均時長為O(N). 這里唯一確定substring用的是頭尾(i,j)表示。因為palindrome的對稱性,我們可以從中間出發向兩邊延展,找到最長的palindrome. 分為ABA, ABBA兩種基本情況。一共有N個位置唯一標記點,調用一次extenPalindrome時間worst case是O(len), 最大也就是中點位置的O(n/2). 總的時間復雜度大致為O(N^2/4) 另外還有一種方法,想法來自于palindrome partition那題。 用一個boolean[i,j]表示(i,j)是否為palindrome, 比較i-1和j+1. 寫過一個,代碼復雜,跑起來特別慢,特別是"aaaaaaa"這種,所以拋棄掉。
public class Solution { private int lo = 0, maxLen = 0; public String longestPalindrome(String s) { if(s.isEmpty()) return null; int len = s.length(); if(len < 2) return s; for(int i=0; i= 0 && k < s.length() && s.charAt(j) == s.charAt(k)){ j--; k++; } // 結束是s(j)!=s(k) // k-1 - (j+1) +1 = k - j -1 if(maxLen < k - j - 1){ lo = j + 1; maxLen = k - j - 1; } } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66906.html
摘要:題目解析題目是要找出最長的回文字符串,拿到題目的第一反應是遍歷子串,然后一直替換最長的子字符串即可了。但是這種解法遇到極端輸入狀況就會超時,指定的最長長度為,遍歷子串需要兩次循環,判斷回文需要一次循環,所以總的效率為,那么極端狀況會超時。 題目 Given a string s, find the longest palindromic substring in s. You may ...
摘要:難度題目是說給出一個字符串求出這個字符串的最長回文的子串回文是指前后完全對稱的字符串像是之類的都算是回文奇數字母的回文和偶數字母的回文中心是不一樣的奇數字母比如的中心在中間字母上偶數字母比如的回文在中間兩字母的中心上由此可見回文中心點實際上 Given a string s, find the longest palindromic substring in s. You may as...
摘要:回文的意思就是反轉字符串后和原字符串相等。因為這種想法沒次都是兩邊同時擴展。所以要分目標字符串長度為奇數目標字符串為偶數兩種情況。 題目詳情 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.題目的意思是輸入...
摘要:這種解法中,外層循環遍歷的是子字符串的中心點,內層循環則是從中心擴散,一旦不是回文就不再計算其他以此為中心的較大的字符串。 Longest Palindromic Substring Given a string S, find the longest palindromic substring in S. You may assume that the maximum length ...
摘要:題目即求最長回文子序列原題鏈接此篇博客僅為學習記錄我的解法及代碼暴力解決,用及進行兩層遍歷循環中套一層循環,用遍歷,求最長回文序列字符串,同時用變量記錄最長子序列這種寫法很暴力,效率很低,一層循環,一層循環,回文序列對比一層,時間復雜度為辣 題目: Given a string s, find the longest palindromic substring in s. You ma...
閱讀 922·2021-10-13 09:48
閱讀 3907·2021-09-22 10:53
閱讀 3114·2021-08-30 09:41
閱讀 1943·2019-08-30 15:55
閱讀 2920·2019-08-30 15:55
閱讀 1839·2019-08-30 14:11
閱讀 2205·2019-08-29 13:44
閱讀 764·2019-08-26 12:23