숫자만 있는 문자열 s가 있다고 가정합니다. 두 개 이상의 비어 있지 않은 부분 문자열로 분할할 수 있는지 여부를 확인하여 해당 부분 문자열의 숫자 값이 증가하지 않는 순서로 있고 모든 인접한 두 부분 문자열의 숫자 값 차이가 1이 되도록 해야 합니다. 예를 들어 다음과 같은 경우 문자열은 s ="0080079"이므로 숫자 값 [80, 79]를 사용하여 ["0080", "079"]로 나눌 수 있습니다. 그리고 값은 내림차순이고 인접한 값은 1만큼 다르므로 이 방법이 유효합니다. 위와 같이 분할이 가능한지 여부를 확인해야 합니다.
따라서 입력이 s ="080076"과 같으면 ["08", "007", "6"]과 같이 분할할 수 있으므로 출력은 True이므로 숫자 값은 [8,7,6]입니다. .
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
dfs() 함수를 정의합니다. s, pre, idx, n
이 필요합니다. -
pre가 -1이 아니고 (s[index idx to end]의 부분 문자열)의 정수 형식이 pre -1과 같으면
-
참을 반환
-
-
범위 1에서 n-idx-1까지의 i에 대해 수행
-
curs :=s의 부분 문자열[인덱스 idx에서 idx+i-1까지]
-
cur :=숫자로 저주
-
pre가 -1과 같으면
-
dfs(s, cur, idx+i, n)가 참이면
-
참을 반환
-
-
그렇지 않으면
-
cur가 pre-1과 같고 dfs(s, cur, idx+i, n)가 참이면
-
참을 반환
-
-
-
-
-
거짓을 반환
-
기본 방법에서 다음을 수행하십시오.
-
n :=s
의 크기 -
n <=1이면
-
거짓을 반환
-
-
반환 dfs(s, -1, 0, n)
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def dfs(s, pre, idx, n):
if pre != -1 and int(s[idx:]) == pre - 1:
return True
for i in range(1, n-idx):
curs = s[idx: idx+i]
cur = int(curs)
if pre == -1:
if dfs(s, cur, idx+i, n):
return True
else:
if cur == pre - 1 and dfs(s, cur, idx+i, n):
return True
return False
def solve(s):
n = len(s)
if n <= 1:
return False
return dfs(s, -1, 0, n)
s = "080076"
print(solve(s))
입력
"080076"
출력
True