Skip to content

Instantly share code, notes, and snippets.

@tombaranowicz
Created September 26, 2019 13:13
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tombaranowicz/7299e33fd8864c2dabb1d0b45dcf66dc to your computer and use it in GitHub Desktop.
Save tombaranowicz/7299e33fd8864c2dabb1d0b45dcf66dc to your computer and use it in GitHub Desktop.
How To Solve LeetCode Longest Palindromic Substring Problem With JavaScript
// OPTIMIZED
function expandAroundCenterSolution(s) {
let start = 0, end = 0;
for (let i = 0; i < s.length; i++) {
let center = getCenter(s, i);
let bounds = expandAroundCenter(s, center[0], center[1]);
let L = bounds[0], R = bounds[1];
if (R - L > end - start) {
start = L;
end = R;
}
console.log("---");
i = center[1]; //move to the end of center, i++ will then shift pointer to index right after current center
}
return s.substring(start, end + 1);
}
function expandAroundCenter(s, left, right) {
let L = left, R = right;
while (L >= 0 && R < s.length && s[L] === s[R]) {
L--;
R++;
}
console.log("expand return " + (L+1) + ":" + (R-1));
return [++L, --R];
}
function getCenter(s,c){
let L = c, R = c;
console.log("get center start index: " + c);
while(s[L] === s[++R] && R <= s.length );
console.log("return " + L + ":" + (R-1));
return [L, --R];
}
// BRUTE FORCE
function isPalindrome(s) {
let k = 0;
let l = s.length - 1;
let isPalindrome = true;
while(k<=l) {
if (!(s.charAt(k) === s.charAt(l))) {
isPalindrome = false;
break;
}
k++;
l--;
}
return isPalindrome;
}
function bruteForce(s) {
let maxPalindrome = "";
for (let i = 0; i <= s.length-1; i++) {
for (let j = i+1; j <= s.length; j++) {
let subStr = s.substring(i, j)
console.log("check: " + subStr);
if (isPalindrome(subStr)) {
console.log(subStr + " is palindrome")
if (subStr.length > maxPalindrome.length) {
maxPalindrome = subStr;
}
}
}
console.log("---");
}
return maxPalindrome;
}
function longestPalindrome(s) {
// let maxPalindrome = bruteForce(s);
let maxPalindrome = expandAroundCenterSolution(s);
return maxPalindrome;
}
let testCase = "cccaba";
console.log("Longest Palindromic Substring: " + longestPalindrome(testCase));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment