LeetCode第五题——求最大回文字符串

发表于 | | 阅读次数:
字数统计: 646 | 阅读时长 ≈ 2

昨晚被某厂实习笔试算法题完虐，在有限时间内的算法编程简直渣到不行，本身不是很难的题竟然也没做出来。总结只有一点，代码量不够。还是得多多锻炼，提高快速编程的思维能力。

笔试题目的第一题就是LeetCode中的这道算法题，心里不由的碎碎念：要是勤快一点先做了，就会是另外一个情况了。

题目描述很简单：就是在一个字符串中寻找最长子回文字符串。

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

定义

回文，就是一个字符串正着念和反着念都一样，比如“abcba”，比如“上海自来水来自还上”，比如“明天到操场….”。

对于这道算法题研究的英文字符串来说，有奇数回文和偶数回文两种情况。奇数回文是指回文字符串是奇数个，比如abcba；偶数回文是指回文字符串是偶数个，比如abba。在设计算法的时候应该把这两种情况都考虑在内。

思路

  1. 将字符串String处理成字符数组char[];
  2. 逐个字符遍历数组，比如遍历到下标为i的字符时：
    • 奇数回文判断：ci-1是否等于ci+1，如果等于则继续向两头递增，记录最长度；
    • 偶数回文判断：ci-1是否等于ci，如果等于则继续向两头递增，记录最长度。
  3. 遍历结束后判断最长的字符串是偶数回文还是奇数回文，按照长度和下标生成返回回文字符串。

实现

我的算法比较简单，个人感觉比较好理解，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class Solution {
	public String longestPalindrome(String s) {
		char[] c = s.toCharArray();
		
		int evenPos = 1,oddPos = 0;
		int evenLen = 0,oddLen = 0;
		
		for (int i = 1; i <= c.length - 1; i++) {
			int oddCount = 0;
			int evenCount = 0;
			// 奇数回文
			while (i - oddCount >= 0 && i + oddCount <= c.length - 1 && c[i - oddCount] == c[i + oddCount]) {
				if (oddCount > oddLen) {
					oddLen = oddCount;
					oddPos = i;
				}
				oddCount++;
			}
			// 偶数回文
			while (i - 1 - evenCount >= 0 && i + evenCount <= c.length - 1 && c[i - 1 - evenCount] == c[i + evenCount]) {
				evenCount++;
				if (evenCount > evenLen) {
					evenLen = evenCount;
					evenPos = i;
				}
			}
		}
		char[] palindromeArray = null;
		if(evenLen>oddLen){
			//输出偶数回文
			palindromeArray = new char[2 * evenLen];
			System.arraycopy(c, evenPos-evenLen, palindromeArray, 0, 2 * evenLen);
		}else{
			//输出奇数回文
			palindromeArray = new char[2 * oddLen + 1];
			System.arraycopy(c, oddPos-oddLen, palindromeArray, 0, 2 * oddLen+1);
		}
		String palindrome = new String(palindromeArray);
		return palindrome;
	}
}
0%