문자열 s가 있다고 가정합니다. 3개의 회문 부분 문자열로 나눌 수 있는지 여부를 확인해야 합니다.
따라서 입력이 s ="levelpopracecar"와 같으면 출력은 "level", "pop", "racecar"와 같이 분할할 수 있으므로 True가 됩니다. 모두 회문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=s
의 크기 -
dp :=n x n 차의 행렬이고 false로 채움
-
n-1 ~ 0 범위의 i에 대해 1 감소, 수행
-
0 ~ n - 1 범위의 j에 대해 수행
-
i>=j이면
-
dp[i, j] :=참
-
-
그렇지 않으면 s[i]가 s[j]와 같을 때
-
dp[i, j] :=dp[i+1, j-1]
-
-
-
범위 1에서 n - 1까지의 i에 대해 수행
-
i+1 ~ n - 1 범위의 j에 대해 수행
-
dp[0, i-1] 및 dp[i, j-1] 및 dp[j, n-1]이 모두 참이면
-
참을 반환
-
-
-
-
-
거짓을 반환
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(s):
n = len(s)
dp = [[False] * n for _ in range(n)]
for i in range(n-1, -1, -1):
for j in range(n):
if i >= j:
dp[i][j] = True
elif s[i] == s[j]:
dp[i][j] = dp[i+1][j-1]
for i in range(1, n):
for j in range(i+1, n):
if dp[0][i-1] and dp[i][j-1] and dp[j][n-1]:
return True
return False
s = "levelpopracecar"
print(solve(s)) 입력
"levelpopracecar"
출력
True