Longest Palindrome In A String

Ran across the Longest Palindrome In A String problem today and tried it out. Saw that there is a linear solution but have yet to try it out. I’ll be trying that out next once I make sense of it.

The first way and lazier way was this n^3:

	boolean isPalindrome(String text)
	{
		boolean result = false;
		StringBuilder sb = new StringBuilder(text);

		StringBuilder sbReverse = sb.reverse();

		int res = (sb.toString().compareTo(text) );
		return (sb.toString().compareTo(text) ) == 0;
	}

	String naive1(String text) {
		String result;

		for (int i = text.length(); i >= 2; i--) {
			for (int j = text.length()-i; j >= 0; j--) {
				if (isPalindrome(text.substring(j,i))) {
					return text.substring(j, i);
				}
			}
		}

		return "";
	}

A better way was this n^2:

	// Returns the longest palindrome around this position
	String longestPalindrome(String text, int position) {
		int len = text.length();
		int left, right;
		StringBuilder sb = new StringBuilder();
		// test position out of bounds
		if (position < 0 || position >= len)
			return null;
		// test if position is one less than length
		if (position == 0 || position == len-1)
			return sb.append(text.charAt(position)).toString();
		// if length is even
		if (len % 2 == 0) {
			left = position;
			right = position+1;
		} else { // odd
			sb.append(text.charAt(position));
			left = position - 1;
			right = position + 1;
		}
		do {
			char cLeft = text.charAt(left);
			if (cLeft == text.charAt(right)) {
				sb.insert(0, cLeft);
				sb.append(cLeft);
				left--;
				right++;
			}
			else
				break;

		} while (left >= 0 && right < len);
		return sb.toString();
	}

	String quadLongestPalindrome(String text) {
		String result = null;
		StringBuffer max = new StringBuffer();
		for (int i = 0; i < text.length(); i++) {
			int maxLen = max.length();
			String palin = longestPalindrome(text, i);
			if (palin.length() > maxLen) {
				max.delete(0, maxLen);
				max.append(palin);
			}

		}
		return max.toString();
	}
Advertisements
This entry was posted in Coding. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s