现在的位置: 首页 > 编程技术 > 算法学习 > 正文

leetcode Longest Palindromic Substring 题解

2016年04月12日 算法学习 ⁄ 共 1079字 ⁄ 字号 leetcode Longest Palindromic Substring 题解已关闭评论 ⁄ 阅读 396 次

https://leetcode.com/problems/longest-palindromic-substring/

1.暴力解法

	public String longestPalindrome(String s) {
		String temp = "";
		for (int i = 0; i < s.length(); i++) { for (int j = s.length() - 1; j >= i; j--) {
				if (temp.length() < (j + 1 - i) && isPalindrome(s.substring(i, j + 1))) {
					temp = s.substring(i, j + 1);
					break;
				}
			}
		}
		return temp;
	}

	public boolean isPalindrome(String s) {
		if (s == null || s.length() == 0) {
			return false;
		}
		char[] temp = s.toCharArray();
		for (int i = 0; i < s.length() / 2 + 1; i++) {
			if (temp[i] != temp[s.length() - i - 1]) {
				return false;
			}
		}
		return true;
	}

2.从回文的中间元素入手向两边对称的搜索,有2n-1种可能,分为回文中间是间隙,如aa,或者为字母,如aba两种情况

	public String longestPalindromen(String s) {
		if (s == null || s.length() == 0 || s.length() == 1) {
			return s;
		}
		String temp = "";
		for (int i = 0; i < 2 * s.length() - 1; i++) {
			if (i % 2 == 0) {
				for (int j = 1; i / 2 + j < s.length() && i / 2 - j > -1; j++) {
					if (s.charAt(i / 2 + j) == s.charAt(i / 2 - j) && temp.length() < 2 * j + 1) {
						temp = s.substring(i / 2 - j, i / 2 + j + 1);
					} else if (s.charAt(i / 2 + j) != s.charAt(i / 2 - j)) {
						break;
					}
				}
			} else {
				for (int j = 1; i / 2 + j < s.length() && i / 2 + 1 - j > -1; j++) {
					if (s.charAt(i / 2 + j) == s.charAt(i / 2 + 1 - j) && temp.length() < 2 * j) {
						temp = s.substring(i / 2 + 1 - j, i / 2 + j + 1);
					} else if (s.charAt(i / 2 + j) != s.charAt(i / 2 + 1 - j)) {
						break;
					}
				}
			}

		}
		return temp;
	}

抱歉!评论已关闭.