-
Notifications
You must be signed in to change notification settings - Fork 1
/
5LongestPalindromicSubstring.cs
183 lines (160 loc) · 6.78 KB
/
5LongestPalindromicSubstring.cs
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _5LongestPalindromicSubstring
{
class Program
{
static void Main(string[] args)
{
}
/*
* http://blog.csdn.net/linhuanmars/article/details/20888595
*
* analysis from the above blog:
* 这道题是比较常考的题目,求回文子串,一般有两种方法。 第一种方法比较直接,
* 实现起来比较容易理解。基本思路是对于每个子串的中心(可以是一个字符,或者
* 是两个字符的间隙,比如串abc,中心可以是a,b,c,或者是ab的间隙,bc的间隙)
* 往两边同时进行扫描,直到不是回文串为止。假设字符串的长度为n,那么中心的个数
* 为2*n-1(字符作为中心有n个,间隙有n-1个)。对于每个中心往两边扫描的复杂度
* 为O(n),所以时间复杂度为O((2*n-1)*n)=O(n^2),空间复杂度为O(1),
*
* julia's comment:
* 1. Write a script to do this brute force solution:
* step 1: base case, string is empty or lenght is 0
* step 2: total cases, 2*len-1, go through each case one time
* two cases: A. one char in center
* B. two char in center
* step 3: each case, call palindrome function once,
* checking from center to both side, left and right two pointers
* step 4: each iteration, refresh maximum length and also string content
*/
public static String longestPalindrome(String s)
{
int len = s.Length;
if (s == null || len == 0) // step 1
return "";
int maxLen = 0;
String res = "";
int centerCount = 2 * len - 1;
for (int i = 0; i < centerCount; i++) // step 2
{
int left = i / 2;
int right = i / 2; // case A: 1 char in center (total n choice)
if (i % 2 == 1) // case B: two chars in the center (total n-1 choice)
right++;
String str = lengthOfPalindrome(s, left, right); // step 3
int l2 = str.Length;
if (maxLen < l2) // step 4
{
maxLen = l2;
res = str;
}
}
return res;
}
/*
* julia's comment:
* 1. go through a loop, starting from input arguments: left, right
* 2. check if left and right is in the string length range,
* 3. if it is, then, left point moves left, right point moves right
* 4. return substring of s with start position and length in C#
*/
private static String lengthOfPalindrome(String s, int left, int right)
{
int len = s.Length;
while (left >= 0 && right < len && s[left] == s[right])
{
left--;
right++;
}
int start = left + 1;
int length = right - left;
return s.Substring(start, length); // C# Substring (int start, int length)
}
/*
* Dynamic programming solution - DP solution
* http://blog.csdn.net/linhuanmars/article/details/20888595
* comment from the above blog:
* 基本思路是外层循环i从后往前扫,内层循环j从i当前字符扫到结尾处。
* 过程中使用的历史信息是从i+1到n之间的任意子串是否是回文已经被记录下来,
* 所以不用重新判断,只需要比较一下头尾字符即可。这种方法使用两层循环,
* 时间复杂度是O(n^2)。而空间上因为需要记录任意子串是否为回文,
* 需要O(n^2)的空间
*
* julia's comment:
* 1. The thought process to use DP method:
* Total problems are n^2 in total, s[i][j] is palindromic, i<=j, s[i][j] is substring s from i to j;
* 1. base case discussion
* 2. construct a two dimension array to express all subproblems - substring are palindormic or not
* using jagged array, default initialization is 0 - false
* 3. construct a two nested loops:
* one loop for i: decreasing order, starting position
* inside loop for j: increasing order, j>==i, ending position
*
* palin[i][j] is about string's substring from position i to j, 0 <= i <= j <= n-1, is palindrome
* if s[i] = s[j], then subproblem of palin[i][j] should be palin[i+1][j-1] is true or not
* (assuming i+1<=j-1 => j-i>=2)
*
* http://www.programcreek.com/2013/12/leetcode-solution-of-longest-palindromic-substring-java/
* start condition:
* table[i][i] == 1;
table[i][i+1] == 1 => s[i] == s[i+1]
*
* Changing condition:
* table[i+1][j-1] == 1 && s[i] == s[j]
=>
table[i][j] == 1
*
* Time complexity: O(n^2), space complexity: O(n^2)
*/
public static String longestPalindrome_2(String s) {
int len = s.Length;
if(s == null || len == 0)
return "";
bool[][] table = new bool[len][];
for (int i = 0; i < len; i++ ) // array table[i][j] stands for DP 2-dimension array
{
table[i] = new bool[len];
}
int maxLen = 0;
String res = "";
//every single letter is palindrome
for (int i = 0; i < len; i++)
{
table[i][i] = true;
}
//e.g. bcba
//two consecutive same letters are palindrome
for (int i = 0; i <= len - 2; i++)
{
if (s[i] == s[i + 1])
{
table[i][i + 1] = true;
res = s.Substring(i, 2);
}
}
//condition for calculate whole table
for (int l = 3; l <= len; l++)
{
for (int i = 0; i <= len - l; i++)
{
int j = i + l - 1;
if (s[i] == s[j])
{
table[i][j] = table[i + 1][j - 1];
if (table[i][j] == true && l > maxLen)
res = s.Substring(i, j -i + 1);
}
else
{
table[i][j] = false;
}
}
}
return res;
}
}
}