Time O(n^2)
感觉并不是太理解这道题
public class Solution {
/**
* @param s input string
* @return the longest palindromic substring
*/
public String longestPalindrome(String s) {
// Write your code here
if (s == null || s.length() == 0) return "";
int len = s.length();
int maxLength = 0, start = 0, end = 0;
//boolean[i][j] means s.substring(i, j + 1) is palindrome or not
boolean[][] isPalind = new boolean[len][len];
int currLength = 0;
for (int right = 0; right < len; right++) {
for (int left = right; left >= 0; left--) {
if (right == left) {
isPalind[left][right] = true;
} else if (s.charAt(left) == s.charAt(right)) {
//next to each other
if (left + 1 == right) {
isPalind[left][right] = true;
} else {
isPalind[left][right] = isPalind[left + 1][right - 1];
}
}
if (isPalind[left][right]) {
currLength = right - left + 1;
if (currLength > maxLength) {
maxLength = currLength;
start = left;
end = right;
}
}
}
}
if (maxLength == 0) return "";
return s.substring(start, end + 1);
}
}
二刷
13.18 %
// only 1 char [Y]
// 2 chars same[Y]
// start1 s2 e2 end1
// a b c.... s a
public class Solution {
public String longestPalindrome(String s) {
//isPalindrome[i][j] -> the substring [i, j] is Palindrome
// if (i + 1 < j) -> isPalindrome[i][j] = char[i] == char[j] && isPalindrome[i + 1][j - 1]
//increase j from 0 to s.length() - 1
//decrease i from i to 0
if (s == null || s.length() == 0) return "";
int start = -1, end = -1;
int i = 0, j = 0;
int max = 0;
int len = s.length();
boolean[][] isPalindrome = new boolean[len][len];
for (j = 0; j < len; j++) {
for (i = j; i >= 0; i--) {
if (i == j) isPalindrome[i][j] = true;
else if (s.charAt(i) == s.charAt(j)) {
if (i + 1 == j) isPalindrome[i][j] = true;
else isPalindrome[i][j] = isPalindrome[i + 1][j - 1];
} else {
isPalindrome[i][j] = false;
}
if (isPalindrome[i][j] && j - i + 1 > max) {
max = j - i + 1;
start = i;
end = j;
}
}
}
if (max == 0) return "";
return s.substring(start, end + 1);
}
}
三刷 6/3/2018
https://articles.leetcode.com/longest-palindromic-substring-part-i/
Previous DP solutions take time O(n^2) and space O(n^2)
If we expand from center, we don't need to use extra space to keep track of isPalindrome[i - 1][ j - 1]
If we go from left to right, we have all together 2length - 1 centers, (i, i)(i, i + 1) are such centers.
We expand our string iff s[i] == s[j], once they are not equal, we know that the current substring is not a valid palindrome any more.
Each expanding can take at most O(n) time, so overall we have (2n - 1)n -> O(n^2) time complexity and O(1) space complexity
beats 93.63 %
class Solution {
private int maxLeft, maxRight;
private int maxLength;
public String longestPalindrome(String s) {
if (s == null) return s;
int max = 0;
for (int i = 0; i < s.length(); i++) {
longestPalindromeHelper(s, i, i);
longestPalindromeHelper(s, i, i + 1);
}
return s.substring(maxLeft + 1, maxRight);
}
private void longestPalindromeHelper(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
if ((right - left - 1) > maxLength) {
maxLength = right - left - 1;
maxLeft = left;
maxRight = right;
}
}
}
四刷
非dp intuitive solution
Runtime: 22 ms, faster than 92.94% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 39.1 MB, less than 73.74% of Java online submissions for Longest Palindromic Substring.
class Solution {
private int maxLen, start;
public String longestPalindrome(String s) {
// To check if a substring is palindrome or not
for (int i = 0; i < s.length(); i++) {
expand(s, i, i);
expand(s, i, i + 1);
}
return s.substring(start, start + maxLen);
}
private void expand(String s, int i, int j) {
while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
i--;
j++;
}
int len = j - i - 1;
if (len > maxLen) {
start = i + 1;
maxLen = len;
}
}
}
五刷 05/2022
Version #1 Intuitive solution without DP
Runtime: 647 ms, faster than 12.42% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 41.9 MB, less than 98.58% of Java online submissions for Longest Palindromic Substring.
class Solution {
// Space O(1)
// Time O(n^3)
private int left = 0, right = 0;
public String longestPalindrome(String s) {
// Enumerate all substrings of the string s
// Check if they are palindrome
// If yes, compare with the longest palindrome and update
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
if ((j - i > right - left)&& isPalin(s, i, j)) {
left = i;
right = j;
}
}
}
return s.substring(left, right + 1);
}
private boolean isPalin(String s, int i, int j) {
// a
// ab, aa
// aba, aac
while (j > i) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
j--;
i++;
}
return true;
}
}
Version #2 DP native
Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming.
Runtime: 508 ms, faster than 17.16% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 86.3 MB, less than 16.42% of Java online submissions for Longest Palindromic Substring.
class Solution {
// Space O(n^2)
// Time O(n^2)
private int left = 0, right = 0;
public String longestPalindrome(String s) {
// aabbaa
// If we've already known that bb is a palindrome, then we can cache and reuse this result in the furhter checks
// For example when checking abba, we can reuse the [bb] is palindrome result and char a == a, so abba is a palindrome too
// The base case is each character itself is a palindrom
// for all i == j, isPalin[i][j] == true
// for all i + 1 == j, is Palin[i][j]: s.charAt(i) == s.charAt(j)
// The recursion formulat is that isPalin[i][j] (i + 1 < j): s.charAt(i) == s.charAt(j) && isPalin[i+1][j-1]
int len = s.length();
boolean[][] cache = new boolean[len][len];
for (int j = 0; j < len; j++) {
for (int i = j; i >= 0; i--) {
if (isPalin(s, cache, i, j) && j - i > right - left) {
left = i;
right = j;
}
}
}
return s.substring(left, right + 1);
}
private boolean isPalin(String s, boolean[][] cache, int i, int j) {
// Invalid case in our scenario
if (i > j) {
return false;
}
if (i == j) {
cache[i][j] = true;
} else if (i + 1 == j) {
cache[i][j] = s.charAt(i) == s.charAt(j);
} else {
cache[i][j] = s.charAt(i) == s.charAt(j) && cache[i + 1][j - 1];
}
return cache[i][j];
}
}
Version #3 Optimized O(n^3) solution
Runtime: 755 ms, faster than 10.06% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 43.5 MB, less than 51.91% of Java online submissions for Longest Palindromic Substring.
class Solution {
public String longestPalindrome(String s) {
// We can start checking from the longest substring length to the shortest length 1
// If a substring with length "len" is a palindrome, then we could return the substring directly
if (s == null) {
return null;
}
// babad
for (int len = s.length(); len >= 1; len--) {
for (int start = 0; start + len - 1 < s.length(); start++) {
if (isPalin(s, start, start + len - 1)) {
return s.substring(start, start + len);
}
}
}
return "";
}
private boolean isPalin(String s, int start, int end) {
// ...a...
// ...aa..., ...ab...
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
}
Version #4 Expand from the center
Runtime: 38 ms, faster than 74.92% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 42.3 MB, less than 91.44% of Java online submissions for Longest Palindromic Substring.
Time O(n^2)
Space O(1)
class Solution {
// Expand around the center
// cabcbad
// We can see from this example that the longest substring is abcba, there's a common substring between abcba and bcb. We could reuse the result of bcb, and expand it from the bcb center. If we failed to expand then bcb will be the longest substring starting from central "c". However if we can successfully expand, then abcba become the longest substring starting from central "c".
// The palindrome can have even or odd number of characters. Which means the center of the palindrome can be either a single character, or between two same characters. E.g. a, and aa
// So there are altogether n + (n - 1) centers
// And we just need to expand these centers to find the longest substrings expanded from those centers
private int start = 0, maxLen = 0;
public String longestPalindrome(String s) {
if (s == null) {
return null;
}
int left = 0, right = 0;
for (int center = 0; center < s.length(); center++) {
expandFromCenter(s, center, center);
expandFromCenter(s, center, center + 1);
}
return s.substring(start, start + maxLen);
}
private void expandFromCenter(String s, int left, int right) {
// The palindrome is between l + 1 and r - 1
// lr
// 012345
// ccaabc
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
if (right - left - 1 > maxLen) {
maxLen = right - left - 1;
start = left + 1;
}
}
}
Version #5 Expand from center without global variable
Runtime: 57 ms, faster than 50.09% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 42.9 MB, less than 70.49% of Java online submissions for Longest Palindromic Substring.
class Solution {
// Expand around the center
// cabcbad
// We can see from this example that the longest substring is abcba, there's a common substring between abcba and bcb. We could reuse the result of bcb, and expand it from the bcb center. If we failed to expand then bcb will be the longest substring starting from central "c". However if we can successfully expand, then abcba become the longest substring starting from central "c".
// The palindrome can have even or odd number of characters. Which means the center of the palindrome can be either a single character, or between two same characters. E.g. a, and aa
// So there are altogether n + (n - 1) centers
// And we just need to expand these centers to find the longest substrings expanded from those centers
public String longestPalindrome(String s) {
if (s == null) {
return null;
}
int maxLen = 0, start = 0;
int len = s.length();
// c = 2
// 012345
// ccaacc
// len1 = 1
// len2 = 6
// left = 0
for (int center = 0; center < len; center++) {
int oddLen = expandFromCenter(s, center, center);
int evenLen = expandFromCenter(s, center, center + 1);
// start...center...end
// oddLen = (center - start + 1) * 2 - 1
// start...center center+1...end
// evenLen = (center - start + 1) * 2
if (oddLen > maxLen) {
maxLen = oddLen;
start = center + 1 - (oddLen + 1 ) / 2;
}
if (evenLen > maxLen) {
maxLen = evenLen;
start = center + 1 - evenLen / 2;
}
}
return s.substring(start, start + maxLen);
}
private int expandFromCenter(String s, int left, int right) {
// lr
// 012345
// ccaabc
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
}
六刷 06/2022
Version #5 Expand from Center
优化了一下，expand的同时update最后的result，代码会简洁一点
Time O(N^2)
Space O(1)
Runtime: 36 ms, faster than 85.66% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 42.4 MB, less than 90.23% of Java online submissions for Longest Palindromic Substring.
class Solution {
public String longestPalindrome(String s) {
int[] startEnd = new int[2];
// Find the longest palindrome expanding from each index
for (int i = 0; i < s.length(); i++) {
expand(s, i, i, startEnd);
expand(s, i, i + 1, startEnd);
}
return s.substring(startEnd[0] + 1, startEnd[1]);
}
private void expand(String s, int i, int j, int[] startEnd) {
if (i > j || i >= s.length() || j >= s.length()) {
return;
}
while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
i--;
j++;
}
// (i, j)
if (j - i > startEnd[1] - startEnd[0]) {
startEnd[0] = i;
startEnd[1] = j;
}
}
}
No comments:
Post a Comment