给定输入字符串,要求判断任意子字符串是否对称。
基本思路就是DP
写出DP表达式为 dp[i][j] = dp[i + 1][j - 1] && (s[i] == s[j]) dp[i][j]代表s(i,j)的子串是否对称
注意在for循环赋值时,这里增长的对象其实是子串的长度。
长度为奇数时:
(->代表决定)
dp[0,0]
dp[1,1] -> dp[0,2]
dp[2,2] -> dp[1,3] -> dp[0,4]
dp[3,3] -> dp[2,4] -> dp[1, 5]
...
长度为偶数时:
dp[0,1]
dp[1,2] -> dp[0,3]
dp[2,3] -> dp[1,4] -> dp[0,5]
dp[3,4] -> dp[2,5] -> dp[1,6]
...
因此外层循环变量是长度,内层循环变量是起点
def palindrom(s):
length = len(s)
# Create a 2D array in Python
dp = [[False for i in range(length)] for j in range(length)]
# length = 1 substring
for i in range(length):
dp[i][i] = True
# length = 2 substring
for i in range(length - 1):
if s[i] == s[i + 1]:
dp[i][i + 1] = True
# length = k substring
for len3 in range(3, length + 1):
for start in range(0, length - len3 + 1):
end = start + len3 - 1
if s[start] == s[end] and dp[start + 1][end - 1]:
dp[start][end] = True print dp
print dp[0][length - 1] palindrom('aaaaabbb')