2014
11-18

LeetCode-Longest Palindromic Substring[字符串]

Longest Palindromic Substring

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.

\begin{Code}
f[i][j] = if (i == j) S[i]
if (S[i] == S[j] && f[i+1][j-1] == S[i+1][j-1]) S[i][j]
else max(f[i+1][j-1], f[i][j-1], f[i+1][j])
\end{Code}

$$f(i,j)=\begin{cases} true & ,i=j\\ S[i]=S[j] & , j = i + 1 \\ S[i]=S[j] \text{ and } f(i+1, j-1) & , j > i + 1 \end{cases}$$

// LeetCode, Longest Palindromic Substring
// 备忘录法，会超时
// 时间复杂度O(n^2)，空间复杂度O(n^2)
typedef string::const_iterator Iterator;

namespace std {
template<>
struct hash<pair<Iterator, Iterator>> {
size_t operator()(pair<Iterator, Iterator> const& p) const {
return ((size_t) &(*p.first)) ^ ((size_t) &(*p.second));
}
};
}

class Solution {
public:
string longestPalindrome(string const& s) {
cache.clear();
return cachedLongestPalindrome(s.begin(), s.end());
}

private:
unordered_map<pair<Iterator, Iterator>, string> cache;

string longestPalindrome(Iterator first, Iterator last) {
size_t length = distance(first, last);

if (length < 2) return string(first, last);

auto s = cachedLongestPalindrome(next(first), prev(last));

if (s.length() == length - 2 && *first == *prev(last))
return string(first, last);

auto s1 = cachedLongestPalindrome(next(first), last);
auto s2 = cachedLongestPalindrome(first, prev(last));

// return max(s, s1, s2)
if (s.size() > s1.size()) return s.size() > s2.size() ? s : s2;
else return s1.size() > s2.size() ? s1 : s2;
}

string cachedLongestPalindrome(Iterator first, Iterator last) {
auto key = make_pair(first, last);
auto pos = cache.find(key);

if (pos != cache.end()) return pos->second;
else return cache[key] = longestPalindrome(first, last);
}
};


// LeetCode, Longest Palindromic Substring
// 动规，时间复杂度O(n^2)，空间复杂度O(n^2)
class Solution {
public:
string longestPalindrome(string s) {
const int n = s.size();
bool f[n][n];
fill_n(&f[0][0], n * n, false);
// 用 vector 会超时
//vector<vector<bool> > f(n, vector<bool>(n, false));
size_t max_len = 1, start = 0;  // 最长回文子串的长度，起点

for (size_t i = 0; i < s.size(); i++) {
f[i][i] = true;
for (size_t j = 0; j < i; j++) {  // [j, i]
f[j][i] = (s[j] == s[i] && (i - j < 2 || f[j + 1][i - 1]));
if (f[j][i] && max_len < (i - j + 1)) {
max_len = i - j + 1;
start = j;
}
}
}
return s.substr(start, max_len);
}
};


// LeetCode, Longest Palindromic Substring
// Manacher’s Algorithm
// 时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
// Transform S into T.
// For example, S = "abba", T = "^#a#b#b#a#$". // ^ and$ signs are sentinels appended to each end to avoid bounds checking
string preProcess(string s) {
int n = s.length();
if (n == 0) return "^$"; string ret = "^"; for (int i = 0; i < n; i++) ret += "#" + s.substr(i, 1); ret += "#$";
return ret;
}

string longestPalindrome(string s) {
string T = preProcess(s);
const int n = T.length();
// 以T[i]为中心，向左/右扩张的长度，不包含T[i]自己，
// 因此 P[i]是源字符串中回文串的长度
int P[n];
int C = 0, R = 0;

for (int i = 1; i < n - 1; i++) {
int i_mirror = 2 * C - i; // equals to i' = C - (i-C)

P[i] = (R > i) ? min(R - i, P[i_mirror]) : 0;

// Attempt to expand palindrome centered at i
while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
P[i]++;

// If palindrome centered at i expand past R,
// adjust center based on expanded palindrome.
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}

// Find the maximum element in P.
int max_len = 0;
int center_index = 0;
for (int i = 1; i < n - 1; i++) {
if (P[i] > max_len) {
max_len = P[i];
center_index = i;
}
}

return s.substr((center_index - 1 - max_len) / 2, max_len);
}
};


1. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count

2. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), [email protected]
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}