Palindrome Examples in JavaScript

palindrome

// naive approach
// Naively, we can simply examine every substring and check if it is palindromic.
// The time complexity is O(n^3).// Therefore, this approach is just a start, we need a better algorithm.
var longestPalindrome1 = function (string) {
	var maxPalinLength = 0,
		longestPalindrome = null,
		length = string.length;

	// check all possible sub strings
	for (var i = 0; i < length; i++) {
		for (var j = i + 1; j < length; j++) {
			var len = j - i;
			var curr = string.substring(i, j + 1);
			if (isPalindrome(curr)) {
				if (len > maxPalinLength) {
					longestPalindrome = curr;
					maxPalinLength = len;
				}
			}
		}
	}
	return longestPalindrome;
};

var isPalindrome = function (string) {
	var length = string.length;
	for (var i = 0; i < length - 1; i++) {
		if (string.charAt(i) !== string.charAt(length - 1 - i)) {
			return false;
		}
	}

	return true;
};

// dynamic
// Let the input string, i and j are two indices of the string.
// Define a 2-dimension array "table" and let table[i][j]
// denote whether a substring from i to j is palindrome.
var longestPalindrome2 = function (string) {
	if (string == null) {
		return null;
	}
	if (string.length <= 1) {
		return string;
	}
	var maxLen = 0,
		longestStr = null,		length = string.length,
 		table = [[]],
 		i = 0;
	//every single letter is palindrome
	for (i = 0; i < length; i++) {
		table[i] = [i];
		table[i][i] = 1;
	}
	// console.table(table);
	//e.g. bcba
	//two consecutive same letters are palindrome
	for (i = 0; i <= length - 2; i++) {
		if (string.charAt(i) === string.charAt(i + 1)) {
			table[i][i + 1] = 1;
			longestStr = string.substring(i, i + 2);
		}
	}
	// console.table(table);

	//condition for calculate whole table
	for (var l = 3; l <= length; l++) {
		for (i = 0; i <= length - l; i++) {
			var j = i + l - 1;
			if (string.charAt(i) === string.charAt(j)) {
				table[i][j] = table[i + 1][j - 1];

				if (table[i][j] == 1 && l > maxLen) {
					longestStr = string.substring(i, j + 1);
				}
			} else {
				table[i][j] = 0;
			}

			// console.table(table);
		}
	}
	return longestStr;
};


// A Simple Algorithm
// Time O(n^2), Space O(1)
var longestPalindrome = function (string) {
	if (string === "") {
		return null;
	}
	if (string.length === 1) {
		return string;
	}
	var longest = string.substring(0, 1);
	for (var i = 0; i < string.length; i++) {
		// get longest palindrome with center of i
		var tmp = helper(string, i, i);
		if (tmp.length > longest.length) {
			longest = tmp;
		}
		// get longest palindrome with center of i, i + 1
		tmp = helper(string, i, i + 1);
		if (tmp.length > longest.length) {
			longest = tmp;
		}
	}
	return longest;
};

// one more function - how does this compare?
var isPalindrome2 = function (s) {
    // Special case: empty strings are not palindromes
    if(!s) { return false; }

    // sanitize string by translating to uppercase and checking only the first line
    // poems that read backwards and forwards are cute, but outside the scope of this fn
    s = s.split('\n').pop().replace(/[^\u00BF-\u1FFF\u2C00-\uD7FF\w\d]/g, "").toUpperCase();

    // compare the first half to the second half
    return s.slice(0, s.length / 2).split("").reverse().join("") === s.slice(Math.ceil(s.length / 2));
}

// Given a center, either one letter or two letter,// Find longest palindrome
var helper = function (string, begin, end) { // string, int, int
	while (begin >= 0 && end <= string.length - 1 && string.charAt(begin) === string.charAt(end)) {
		begin--;
		end++;
	};

	return string.substring(begin + 1, end);
};

var palindrome,
	palindromeTest1,
	palindromeTest2;

var functions = [longestPalindrome, longestPalindrome1, longestPalindrome2, longestPalindrome3];
var palindromes = ["", "tacocat", "Amor, Roma", "dabcba", "racecar", "Racecar", "race,car", " race, car", "anna", "ånnå", "ånna", "ånné", "Ah, Satan sees Natasha!"];
for (var index = 0; index < palindromes.length; index++) {
	var testPalindrome = palindromes[index];
	console.log("testPalindrome: ", testPalindrome);
	for (var i = 0; i < functions.length; i++) {
		var testPalindromeFunc = functions[i];
		console.log("testPalindromeFunc: ", testPalindromeFunc.name, testPalindromeFunc.call(null, testPalindrome));
	}
}

palindrome = "tacocat";
palindromeTest1 = longestPalindrome1(palindrome);
palindromeTest2 = longestPalindrome2(palindrome);
palindromeTest3 = longestPalindrome(palindrome);
console.log(palindromeTest1);
console.log(palindromeTest2);
console.log(palindromeTest3);

palindrome = "Amor, Roma"; // fails on sentences
palindromeTest1 = longestPalindrome1(palindrome);
palindromeTest2 = longestPalindrome2(palindrome);
palindromeTest3 = longestPalindrome(palindrome);
console.log(palindromeTest1);
console.log(palindromeTest2);
console.log(palindromeTest3);

palindrome = "dabcba";
palindromeTest1 = longestPalindrome1(palindrome);
palindromeTest2 = longestPalindrome2(palindrome);
palindromeTest3 = longestPalindrome(palindrome);
console.log(palindromeTest1);
console.log(palindromeTest2);
console.log(palindromeTest3);