Commit038112c

authored

Update palindrome-partitioning-iv.py

1 parentb4fd8b3 commit038112cCopy full SHA for 038112c

File tree

-6

lines changed

-6

lines changed

Lines changed: 5 additions & 6 deletions

Original file line number	Diff line number	Diff line change
`@@ -10,21 +10,20 @@ def checkPartitioning(self, s):`
`10`	`10`	`defmodified_manacher(s):`
`11`	`11`	`s='^#'+'#'.join(s)+'#$'`
`12`	`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] is composed of 2 palindromic strings`
	`13`	`+dp= [0]*len(s)# dp[i]: s[:i] is composed of dp[i] palindromic strings`
`15`	`14`	`C,R=0,0`
`16`	`15`	`foriinxrange(1,len(s)-1):`
`17`	`16`	`i_mirror=2*C-i`
`18`	`17`	`ifR>i:`
`19`	`18`	`P[i]=min(R-i,P[i_mirror])`
`20`	`19`	`whiles[i+1+P[i]]==s[i-1-P[i]]:`
`21`		`-ifdp1[i-1-P[i]]:`
`22`		`-dp2[(i+1+P[i])+1]=True`
	`20`	`+ifdp[i-1-P[i]]:`
	`21`	`+dp[(i+1+P[i])+1]=dp[i-1-P[i]]+1`
`23`	`22`	`P[i]+=1`
`24`		`-ifi+1+P[i]==len(s)-1anddp2[(i-1-P[i])+1]:`
	`23`	`+ifi+1+P[i]==len(s)-1anddp[(i-1-P[i])+1]==2:`
`25`	`24`	`returnTrue`
`26`	`25`	`ifi-1-P[i]==0:`
`27`		`-dp1[i+1+P[i]]=True`
	`26`	`+dp[i+1+P[i]]=1`
`28`	`27`	`ifi+P[i]>R:`
`29`	`28`	`C,R=i,i+P[i]`
`30`	`29`	`returnFalse`

Comments

(0)