Find the Median of Two Sorted Arrays - Leet Code Solution
Problem Statement There are two sorted arrays nums1 and nums2 of size m and n…
August 27, 2019
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
Simple!
public class Q5_LongestPalindromeSubstring_Simple {
private String str;
public Q5_LongestPalindromeSubstring_Simple(String str) {
this.str = str;
}
private boolean isPalindrome(String s) {
int lastIndex = s.length()-1;
int startIndex = 0;
while (startIndex < s.length() && lastIndex >= 0) {
if (s.charAt(startIndex) != s.charAt(lastIndex)) {
return false;
}
startIndex ++;
lastIndex --;
}
return true;
}
public String longestPalindrome() {
String max = "";
//generate all substrings
for (int i=0; i<this.str.length(); i++) {
for (int j=i+1; j<this.str.length(); j++) {
String substring = this.str.substring(i, j);
if (this.isPalindrome(substring)) {
if (max.length() < substring.length()) {
max = substring;
}
}
}
}
return max;
}
}
It is O(n^3)
For optimized solutions, we should go deeper into the requirements. What is palindrome. It can be found in two ways:
The solution is around starting from the one element, and try to expand it from both sides. Expand it till you find same character.
public class Q5_LongestPalindromeSubstring_Optimized {
private String str;
public Q5_LongestPalindromeSubstring_Optimized(String str) {
this.str = str;
}
//expanding around elements passed
private String findPalindrome(int startIndex, int endIndex) {
String palindrome = "";
while (startIndex >= 0 && endIndex < this.str.length() && this.str.charAt(startIndex) == this.str.charAt(endIndex)) {
palindrome = this.str.substring(startIndex, endIndex+1);
startIndex --;
endIndex ++;
}
return palindrome;
}
public String longestPalindrome() {
String max = "";
for (int i=0; i<this.str.length()-1; i++) {
String s1 = this.findPalindrome(i, i);
String s2 = this.findPalindrome(i, i+1);
String maxOfTwo = s1.length() > s2.length() ? s1 : s2;
if (max.length() < maxOfTwo.length()) {
max = maxOfTwo;
}
}
return max;
}
}
Problem Statement There are two sorted arrays nums1 and nums2 of size m and n…
Big-O notation In simpler terms, its kind of a unit to measure how efficient an…
Problem Statement Given a string, determine if it is a palindrome, considering…
In this post, we will see some of the frequently used concepts/vocabulary in…
Problem Statement Given an array nums of n integers and an integer target, find…
Problem Statement Determine whether an integer is a palindrome. An integer is a…
Introduction This post has the complete code to send email through smtp server…
Introduction In a normal email sending code from python, I’m getting following…
Introduction In one of my app, I was using to talk to . I have used some event…
Introduction So you have a Django project, and want to run it using docker image…
Introduction It is very important to introduce few process so that your code and…
Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…