|
| 1 | +# Time: O(n) |
| 2 | +# Space: O(n) |
| 3 | + |
| 4 | +classSolution(object): |
| 5 | +defcheckPartitioning(self,s): |
| 6 | +""" |
| 7 | + :type s: str |
| 8 | + :rtype: bool |
| 9 | + """ |
| 10 | +defmodified_manacher(s): |
| 11 | +s='^#'+'#'.join(s)+'#$' |
| 12 | +P= [0]*len(s) |
| 13 | +dp1= [False]*len(s)# dp1[i]: s[:i] is a palindromic string |
| 14 | +dp2= [False]*len(s)# dp2[i]: s[:i+1] is composed of 2 palindromic strings |
| 15 | +C,R=0,0 |
| 16 | +foriinxrange(1,len(s)-1): |
| 17 | +i_mirror=2*C-i |
| 18 | +ifR>i: |
| 19 | +P[i]=min(R-i,P[i_mirror]) |
| 20 | +whiles[i+1+P[i]]==s[i-1-P[i]]: |
| 21 | +ifdp1[i-1-P[i]]: |
| 22 | +dp2[i+1+P[i]]=True |
| 23 | +P[i]+=1 |
| 24 | +ifi+1+P[i]==len(s)-1anddp2[i-1-P[i]]: |
| 25 | +returnTrue |
| 26 | +ifi-1-P[i]==0: |
| 27 | +dp1[i+1+P[i]]=True |
| 28 | +ifi+P[i]>R: |
| 29 | +C,R=i,i+P[i] |
| 30 | +returnFalse |
| 31 | + |
| 32 | +returnmodified_manacher(s) |
| 33 | + |
| 34 | + |
| 35 | +# Time: O(n^2) |
| 36 | +# Space: O(n) |
| 37 | +classSolution(object): |
| 38 | +defcheckPartitioning(self,s): |
| 39 | +""" |
| 40 | + :type s: str |
| 41 | + :rtype: bool |
| 42 | + """ |
| 43 | +dp= [[False]*len(s)for_inxrange(len(s))] |
| 44 | +foriinreversed(xrange(len(s))): |
| 45 | +forjinxrange(i,len(s)): |
| 46 | +ifs[i]==s[j]and (j-i<2ordp[i+1][j-1]): |
| 47 | +dp[i][j]=True |
| 48 | +foriinxrange(1,len(s)): |
| 49 | +forjinxrange(i+1,len(s)): |
| 50 | +ifdp[0][i-1]anddp[i][j-1]anddp[j][-1]: |
| 51 | +returnTrue |
| 52 | +returnFalse |