소문자와 다른 정수 'j'로 구성된 문자열 'i'가 있다고 가정합니다. 'i'의 크기와 같고 사전순으로 'i'보다 작거나 같으며 'j'보다 큰 연속 등호 문자가 없는 문자열이 몇 개 있는지 알아내야 합니다.
답은 10 ^ 9 + 7로 Mod 결과를 찾아 계산해야 합니다.
따라서 입력이 i ="app", j =2와 같으면 출력은 405가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
j <=0이면
-
0 반환
-
-
m :=10 ^ 9 + 7
-
n :=i의 크기
-
nums :=s에 있는 각 문자에 대한 (문자의 유니코드 표현 - "a"의 유니코드 표현)을 포함하는 새 목록
-
반환 dp(0, True, -1, 0) mod m
-
dp() 함수를 정의합니다. 이것은 pos, bound, last, count가 필요합니다.
-
count> j가 0이 아니면
-
0 반환
-
-
pos가 n과 같으면
-
1 반환
-
-
num :=nums[pos]
-
해상도 :=0
-
범위 0에서 (바인딩된 경우 num + 1, 그렇지 않으면 26) 범위에 있는 i에 대해
-
res :=res + dp(pos + 1, bound이고 i가 num, i, count와 같으면 참 *(i가 last와 같으면 참) + 1)
-
-
반환 해상도
-
-
기본 메서드에서 dp(0, True, -1, 0) % m
을 반환합니다.
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class Solution:
def solve(self, s, k):
if k <= 0:
return 0
MOD = 10 ** 9 + 7
n = len(s)
nums = [ord(char) - ord("a") for char in s]
def dp(pos, bound, last, count):
if count > k:
return 0
if pos == n:
return 1
num = nums[pos]
res = 0
for i in range(num + 1 if bound else 26):
res += dp(pos + 1, bound and i == num, i, count * (i == last) + 1)
return res
return dp(0, True, -1, 0) % MOD
ob = Solution()
print(ob.solve('app',2)) 입력
i = "app" j = 2
출력
405