p5

发表于 | 分类于 |

LeetCode p5 Longest Palindromic Substring 题解

1.题目：

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: “babad”

Output: “bab”

Note: “aba” is also a valid answer.
Example:

Input: “cbbd”

Output: “bb”

题意：

输入一个字符串，输出他的最长回文子串。

2.解题思路:

dp
见代码orz。。以前做过这题的感觉。

3.代码

[title] [] [url] [link text]
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
 
public class Solution {
    public int max = 1;
	public int l = 0;
	public int r = 0;

	public String longestPalindrome(String s) {

		if (s.length() < 1)
			return null;
		char[] c = s.toCharArray();
		for (int i = 0; i < c.length; i++) {
			dp(i, i + 1, c, 0);
			dp(i - 1, i + 1, c, 1);
		}
		return s.substring(l, r + 1);
	}

	public void dp(int left, int right, char[] c, int count) {

		if (left < 0 || right >= c.length || c[left] != c[right]) {
			if (count > max) {
				l = left + 1;
				r = right - 1;
				max = count;
			}
			return;
		}
		dp(left - 1, right + 1, c, count + 2);
	}
}

4.一些总结：

leetcode 200斩。。一只努力奋斗的渣渣