Problem
https://leetcode.com/problems/longest-palindromic-substring/
Answer
O(N^3)
class Solution {
private:
bool check(string &subString, int subStringSize){
int i = 0;
while(i < j) {
if(subString[i] != subString[j]) {
return false;
}
i++;
j--;
}
return true;
}
public:
string longestPalindrome(string s) {
int inputStringSize = s.size();
vector<string> substrings;
for (int i = 0; i < inputStringSize; i++) {
string tmp = "";
for (int j = i; j < inputStringSize; j++) {
tmp += s[j];
substrings.push_back(tmp);
}
}
int maxLength = 0;
string longestSubstring = substrings[0];
int subStringsSize = substrings.size();
for (int i = 0; i < subStringsSize; i++) {
int subStringSize = substrings[i].size();
if(check(substrings[i], subStringSize - 1)){
if(subStringSize > maxLength){
maxLength = subStringSize;
longestSubstring = substrings[i];
}
}
}
return longestSubstring;
}
};
Let's consider the solution to this problem.
The problem can be solved by checking all substrings. We determine whether a substring is palindromic by checking if the characters from the head of the substring and the end of the substring, moving towards the middle, are the same.
For instance, let's split the string babd into all possible substrings:
b, ba, bab, babd
ab, abd, bd, d
Now we'll check whether the characters from the head of the substring and the end of the substring are the same, up to the middle of the substring.
For example:
b is a palindromic substring because the first (b) and last (b) characters are the same.
ba is not a palindromic substring because the first (b) and last (a) characters are not the same.
bab is a palindromic substring because the first (b) and last (b) characters are the same.
babd is not a palindromic substring because the first (b) and last (d) characters are not the same.
We continue this process for all substrings.
However, this solution has suboptimal performance because it has a time complexity of O(n^2) for creating all substrings and O(n) for checking whether a substring is palindromic.
There is a solution with time complexity O(n^2) only. Let's explore this solution.
O(N^2)
class Solution {
private:
bool solve(vector<vector<bool>> &dp, int startIndex, int endIndex, string &inputString){
if(startIndex == endIndex){
return dp[startIndex][endIndex] = true;
}
if(endIndex - startIndex == 1){
if(s[startIndex] == s[endIndex]){
return dp[startIndex][endIndex] = true;
}
else{
return dp[startIndex][endIndex] = false;
}
}
if(s[startIndex] == s[endIndex] && dp[startIndex + 1][endIndex - 1] == true){
return dp[startIndex][endIndex] = true;
} else {
return dp[startIndex][endIndex] = false;
}
}
public:
string longestPalindrome(string s) {
int inputStringSize = s.size();
int startIndexOfMaxLength = 0; int maxLength = 0;
vector<vector<bool>> dp(inputStringSize, vector<bool>(inputStringSize, false));
for(int g = 0; g < inputStringSize; g++){
for(int startIndex = 0, endIndex = g; endIndex < inputStringSize; startIndex++, endIndex++){
solve(dp, startIndex, endIndex, s);
if(dp[startIndex][endIndex] == true){
if(endIndex - startIndex + 1 > maxLength){
startIndexOfMaxLength = startIndex;
maxLength = endIndex - startIndex + 1;
}
}
}
}
return inputStringSize.substr(startIndexOfMaxLength, maxLength);
}
};
This solution use dynamic programming.
It solve a problem that is split to small problem and preserve answer of small problem as memo.
Let's see the inside solution.
string longestPalindrome(string s) {
int inputStringSize = s.size();
int startIndex = 0; int maxLength = 0;
vector<vector<bool>> dp(inputStringSize, vector<bool>(inputStringSize, false));
inputStringSize variable is length of s that is an argument.
startIndex variable is head index of target string.
maxLength variable is the longest palindrome string.
dp variable is an answer that is preserved small programing as memo and it is preserved an answer as two dimencional array.
Next let's see the solve function that is used in double loop.
bool solve(vector<vector<bool>> &dp, int startIndex, int endIndex, string &inputString){
if(startIndex == endIndex){
return dp[startIndex][endIndex] = true;
}
if(endIndex - startIndex == 1){
if(s[startIndex] == s[endIndex]){
return dp[startIndex][endIndex] = true;
}
else{
return dp[startIndex][endIndex] = false;
}
}
if(s[startIndex] == s[endIndex] && dp[startIndex + 1][endIndex - 1] == true){
return dp[startIndex][endIndex] = true;
} else {
return dp[startIndex][endIndex] = false;
}
}
It assignments true to dp[startIndex][endIndex] if startIndex equals endIndex.
For example:
If startIndex is 0 and endIndex is 0, inputString is one word. It equals palindromic string.
if(endIndex - startIndex == 1){
if(s[startIndex] == s[endIndex]){
return dp[startIndex][endIndex] = true;
}
else{
return dp[startIndex][endIndex] = false;
}
}
It assignments true to dp[startIndex][endIndex] if endIndex - startIndex equals 1 and s[StartIndex] equals s[endIndex].
For example:
If s is aa, startIndex is 0 and endIndex is 1, endIndex(1) - startIndex(0) equals 1 and s[0] is a and s[1] is a that equal each other.
It's palindromic string.
It assignments false to dp[startIndex][endIndex] if endIndex - startIndex equals 1 and s[StartIndex] doesn't equal s[endIndex].
For example:
If s is ab, startIndex is 0 and endIndex is 1, endIndex(1) - startIndex(0) equals 1 and s[0] is a and s[1] is b that doesn't equal each other.
It's not palindromic string.
if(s[startIndex] == s[endIndex] && dp[startIndex + 1][endIndex - 1] == true){
return dp[startIndex][endIndex] = true;
} else {
return dp[startIndex][endIndex] = false;
}
It assignments true to dp[startIndex][endIndex] if s[startIndex] and s[endIndex] equal and dp[startIndex + 1][endIndex - 1] is true.
For example:
If s is aba, startIndex is 0 and endIndex is 2, s[startIndex] and s[endIndex] equal.
If s is aba and dp[0 + 1][2 - 1] is true, It's palindromic string.
dp[1][1] already is calculated because it is calculated from small substring. dp[1][1] is true because dp[1][1] is b.
It assignments false to dp[startIndex][endIndex] if s[startIndex] and s[endIndex] don't equal or dp[startIndex + 1][endIndex - 1] is not true.
For example:
If s is abcd, startIndex is 0, endIndex is 3 and dp[0 + 1][3 - 1] is false, It's not palindromic string.
dp[1][2] already is calculated because it is calculated from small substring. dp[1][2] is false because dp[1][2] is bc.
for(int g = 0; g < inputStringSize; g++){
for(int i = 0, j = g; j < inputStringSize; i++, j++){
solve(dp, i, j, s);
The loop perform the solve function to all substring from one word to all words.
For example:
inputStringSize is aba.
First, solve(dp, 0, 0, aba). dp[0][0] is true because substring is a.
Second, solve(dp, 1, 1, aba). dp[1][1] is true because substring is b.
Third, solve(dp, 2, 2, aba). dp[2][2] is true because substring is a.
solve(dp, 0, 1, aba). dp[0][1] is false because substring is ab.
solve(dp, 1, 2, aba). dp[1][2] is false because substring is ba.
solve(dp, 0, 2, aba). dp[0][2] is true because substring is aba.
if(dp[startIndex][endIndex] == true){
if(endIndex - startIndex + 1 > maxLength){
startIndexOfMaxLength = startIndex;
maxLength = endIndex - startIndex + 1;
}
}
It reassignment startIndex to startIndexOfMaxLength and endIndex - startIndex + 1 to maxLength if dp[startIndex][endIndex] that is calculated in the solve function is true and endIndex - startIndex + 1 that is maxLength is bigger than current maxLength.
Finally, longestPalindrome function returns inputStringSize.substr(startIndexOfMaxLength, maxLength) that is the longest palindromic substring.
Top comments (0)