gaoxiao
BAN USERI think this can be done in O(n):
1.we can use a stack, traverse the arr from 0 -> n-1, for every val, if val <= top of stack, pop out the top, and the top to the child list of curr. Do this until top of stack < val or stack is empty.
2.At end, all the value in stack's target is 0, and the target of 'children of this value ' is +1.
3. Every node get visited at most twice, so is O(n).
see my python code:
def main():
ar = [1,3,2,4,5,4,2]
n = len(ar)
q = []
# val, idx, ans, children
q.append((ar[0], 0, 0, []))
for i in xrange(1, n):
curr = (ar[i], i, 0, [])
while len(q) > 0 and ar[i] <= q[len(q) - 1][0]:
tp = q.pop()
curr[3].append(tp)
q.append(curr)
ans = [0] * n
for x in q:
idx = x[1]
tar = x[2]
chi = x[3]
ans[idx] = tar
for c in chi:
q.append((c[0], c[1], c[2] + tar + 1, c[3]))
print ans
I think Manacher algo can solve this in O(n):
(I treat single character as palindrome)
int longestPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
stringstream ss;
int n = s.size();
ss << "#";
for(int i = 0; i < n; i++){
ss << s[i] << "#";
}
string ns = ss.str();
int ret = 0;
vector<int> arr(ns.size(), 0);
int cm = 0;
int ci = 0;
for(int i = 0; i < ns.size(); i++){
int pi = 2 * ci - i;
int pl = 0;
if(pi >= 0){
pl = arr[pi];
}
if(i + pl < cm){
arr[i] = pl;
}else{
while(i + pl < ns.size() && i - pl >= 0){
if(ns[i + pl] != ns[i - pl]) break;
else pl++;
}
pl -= 1;
arr[i] = pl;
if(pl > cm) cm = pl;
}
ret += (arr[i] + 1) / 2;
}
return ret;
}
I think Manacher algo can solve this in O(n), I implement two algos:
1. longestPalindrome is O(n) using Manacher
2. partition is O(n^2) using 2-order DP
#include <stdio.h>
#include <iostream>
#include "climits"
#include "vector"
#include "cstring"
#include <sstream>
#include "cstdlib"
#include "map"
#include "algorithm"
#include "cmath"
#include "queue"
#include "stack"
using namespace std;
class Solution {
public:
int longestPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
stringstream ss;
int n = s.size();
ss << "#";
for(int i = 0; i < n; i++){
ss << s[i] << "#";
}
string ns = ss.str();
int ret = 0;
vector<int> arr(ns.size(), 0);
int cm = 0;
int ci = 0;
for(int i = 0; i < ns.size(); i++){
int pi = 2 * ci - i;
int pl = 0;
if(pi >= 0){
pl = arr[pi];
}
if(i + pl < cm){
arr[i] = pl;
}else{
while(i + pl < ns.size() && i - pl >= 0){
if(ns[i + pl] != ns[i - pl]) break;
else pl++;
}
pl -= 1;
arr[i] = pl;
if(pl > cm) cm = pl;
}
ret += (arr[i] + 1) / 2;
}
return ret;
}
int partition(string s) {
int n = s.size();
vector< vector< bool > > palindromeMatrix(n, vector<bool>(n, false));
for (int i = 0; i < n; i++) {
palindromeMatrix[i][i] = true;
}
int ret = n;
for (int margin = 1; margin < n; margin++) {
for (int i = 0; i < n - margin; i++) {
int j = i + margin;
if ((i + 1 > j - 1 || palindromeMatrix[i + 1][j - 1])
&& s[i] == s[j]) {
palindromeMatrix[i][j] = true;
palindromeMatrix[j][i] = true;
ret += 1;
}
}
}
return ret;
}
};
int main(int argc, char** argv) {
Solution ss;
string s = "abaaba";
cout << ss.longestPalindrome(s) << endl;
cout << ss.partition(s) << endl;
}
I think we can use 2-order DP, here is my python code:
def mat(s, p):
ps = []
for c in p:
if c != '*' and c != '+':
ps.append(c)
else:
prev = ps[len(ps) - 1]
ps.pop()
ps.append(c + prev)
m = len(ps)
n = len(s)
arr = [[False] * (n + 1) for i in xrange(m + 1)]
# init
arr[0][0] = True
for i in xrange(m):
if ps[i][0] == '*':
arr[i + 1][0] = arr[i][0]
# DP
for i in xrange(m):
for j in xrange(n):
currs = s[j]
tmp = False
if ps[i][0] == '*':
currp = ps[i][1]
if currp == currs:
# use 0, 1, n times
tmp |= arr[i][j] | arr[i][j + 1] | arr[i + 1][j]
else:
# can only use 0 time
tmp |= arr[i][j + 1]
elif ps[i][0] == '+':
currp = ps[i][1]
if currp == currs:
# use 1, n times
tmp |= arr[i][j] | arr[i + 1][j]
else:
currp = ps[i]
if currp == currs:
# must match
tmp |= arr[i][j]
arr[i + 1][j + 1] = tmp
return arr[m][n]
nice!
- gaoxiao October 23, 2013