132. 분할 문자열 II
2309 단어 Leetcode
Q:
문자열 s를 지정하고, s를 일부 하위 문자열로 나누어, 모든 하위 문자열이 회문 문자열이 되도록 합니다.
요구에 부합되는 최소 분할 횟수를 되돌려줍니다.
예:
입력: "aab"출력: 1 해석: 한 번 분할하면 s를 ["aa", "b"] 두 개의 회문 서브열로 분할할 수 있습니다.
A:
1. 나는 처음에 DP를 두 번 하려고 생각했다. 먼저 회문수의 dp수조인지 아닌지를 계산하고 원하는 DP를 계산한다.그러나 두 번째 DP 그룹은 내가 사용하는 2차원 그룹으로 O(N^3) 시간이 되었다.그 중에서 모든 원소는 왼쪽 경계에서 오른쪽 경계로 옮겨다니며 분할해야 하기 때문에 첫 번째 DP의 데이터를 이용할 수 있을 줄은 생각하지 못했다.코드가 맞아요. 자기 기계가 도망갔어요. 그런데 AC가 안 돼요. 26번째 용례가 시간을 초과했어요.class Solution:
def minCut(self, s: str) -> int:
# dp
#dp[i][j] s[i,j]
l=len(s)
if not s:
return 0
dp=[[0 for i in range(l)] for j in range(l)]
for i in range(l):
dp[i][i]=1 # ，
for i in range(l-1):
if s[i]==s[i+1]:
dp[i][i+1]=1 # ，
for step in range(2,l):
i=0
while i+step
2. 정확한 코드: 첫 번째 dp수조와 마찬가지로 2차원이어야 한다.두 번째 dp수 그룹은 1차원이고 dp2[i]는 i부터 끝까지 문자열의 최소 분할수를 나타낸다. 각 dp[i]에 대해 i+1에서 n-1까지 분할점 k를 찾으면 끝난다. i에서 k는 회문열로 첫 번째 DP수 그룹을 통해 조회한다. O(1), 나머지 k에서 n-1은 이전에 계산한 것이고 두 번째 DP수 그룹은 오른쪽에서 왼쪽으로 계산해야 한다. 오른쪽 경계가 움직이지 않기 때문이다.전체 O(N^2) 복잡성class Solution:
def minCut(self, s: str) -> int:
l=len(s) # dp ，dp[i][j] s[i,j]
if not l:
return 0
dp=[[0 for i in range(l)] for j in range(l)]
for i in range(l-1,-1,-1): # ，
for j in range(l-1,i-1,-1):
if s[i]==s[j]:
dp[i][j]=1 if j-i<2 else dp[i+1][j-1]
dp2=[float('inf') for i in range(l)] #dp2[i] i
for i in range(l-1,-1,-1):
if dp[i][l-1]: #
dp2[i]=0
else:
_min=float('inf')
for cut in range(i,l-1): #
if dp[i][cut]==1:
_min=min(dp2[cut+1]+1,_min)
dp2[i]=_min
print(dp2)
return dp2[0]
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 문제풀이 노트 113.경로 총 II
경로 총 II
제목 요구 사항
문제풀이
두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예: 다음과 같은 두 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
1. 나는 처음에 DP를 두 번 하려고 생각했다. 먼저 회문수의 dp수조인지 아닌지를 계산하고 원하는 DP를 계산한다.그러나 두 번째 DP 그룹은 내가 사용하는 2차원 그룹으로 O(N^3) 시간이 되었다.그 중에서 모든 원소는 왼쪽 경계에서 오른쪽 경계로 옮겨다니며 분할해야 하기 때문에 첫 번째 DP의 데이터를 이용할 수 있을 줄은 생각하지 못했다.코드가 맞아요. 자기 기계가 도망갔어요. 그런데 AC가 안 돼요. 26번째 용례가 시간을 초과했어요.
class Solution:
def minCut(self, s: str) -> int:
# dp
#dp[i][j] s[i,j]
l=len(s)
if not s:
return 0
dp=[[0 for i in range(l)] for j in range(l)]
for i in range(l):
dp[i][i]=1 # ，
for i in range(l-1):
if s[i]==s[i+1]:
dp[i][i+1]=1 # ，
for step in range(2,l):
i=0
while i+step2. 정확한 코드: 첫 번째 dp수조와 마찬가지로 2차원이어야 한다.두 번째 dp수 그룹은 1차원이고 dp2[i]는 i부터 끝까지 문자열의 최소 분할수를 나타낸다. 각 dp[i]에 대해 i+1에서 n-1까지 분할점 k를 찾으면 끝난다. i에서 k는 회문열로 첫 번째 DP수 그룹을 통해 조회한다. O(1), 나머지 k에서 n-1은 이전에 계산한 것이고 두 번째 DP수 그룹은 오른쪽에서 왼쪽으로 계산해야 한다. 오른쪽 경계가 움직이지 않기 때문이다.전체 O(N^2) 복잡성
class Solution:
def minCut(self, s: str) -> int:
l=len(s) # dp ，dp[i][j] s[i,j]
if not l:
return 0
dp=[[0 for i in range(l)] for j in range(l)]
for i in range(l-1,-1,-1): # ，
for j in range(l-1,i-1,-1):
if s[i]==s[j]:
dp[i][j]=1 if j-i<2 else dp[i+1][j-1]
dp2=[float('inf') for i in range(l)] #dp2[i] i
for i in range(l-1,-1,-1):
if dp[i][l-1]: #
dp2[i]=0
else:
_min=float('inf')
for cut in range(i,l-1): #
if dp[i][cut]==1:
_min=min(dp2[cut+1]+1,_min)
dp2[i]=_min
print(dp2)
return dp2[0]
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 문제풀이 노트 113.경로 총 II경로 총 II 제목 요구 사항 문제풀이 두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다. 설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다. 예: 다음과 같은 두 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
