모든 요소의 길이가 같은 단어라는 문자열 목록이 있다고 가정합니다. target이라는 문자열도 있습니다. 다음 규칙에 따라 주어진 단어를 사용하여 대상을 생성해야 합니다 -
-
왼쪽에서 오른쪽으로 타겟을 생성해야 합니다.
-
target[i]가 words[j][k]와 같을 때, target의 i번째 문자(0-indexed)를 얻기 위해 j번째 문자열의 k번째 문자를 단어로 선택할 수 있습니다.
-
j번째 문자열의 k번째 문자를 사용하면 x <=k인 단어에서 문자열의 x번째 문자를 사용할 수 없습니다.
-
전체 대상 문자열을 형성할 때까지 이 과정을 반복합니다.
따라서 우리는 단어에서 목표를 얻는 방법의 수를 찾아야 합니다. 답이 매우 클 수 있으므로 모듈로 10^9 + 7을 반환합니다.
따라서 입력이 단어 =["pqqp","qppq"], 대상 ="qpq"인 경우 출력은 4가 됩니다.
-
"qpq" -> 인덱스 0("qppq"), 인덱스 1("qppq"), 인덱스 2("pqqp")
-
"qpq" -> 인덱스 0("qppq"), 인덱스 1("qppq"), 인덱스 3("qppq")
-
"qpq" -> 인덱스 0("qppq"), 인덱스 2("qppq"), 인덱스 3("qppq")
-
"qpq" -> 인덱스 1("pqqp"), 인덱스 2("qppq"), 인덱스 3("qppq")
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
m :=단어 수,
-
n :=타겟의 크기
-
d :=m개의 다른 빈 맵으로 채워진 크기 m의 목록
-
단어의 각 w에 대해 수행
-
w의 각 인덱스 j와 단어 c에 대해 수행
-
d[j, c] :=d[j, c] + 1
-
-
-
dfs() 함수를 정의합니다. 이것은 i, j가 걸릴 것입니다
-
i가 n과 같으면
-
1 반환
-
-
i가 m과 같으면
-
0 반환
-
-
return (dfs(i, j+1) + dfs(i+1, j+1) * d[j, target[i]]) mod (10^9 + 7)
-
기본 메서드에서 dfs(0, 0)
를 반환합니다.
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
from collections import Counter def solve(words, target): m, n = len(words[0]), len(target) d = [Counter() for _ in range(m)] for w in words: for j, c in enumerate(w): d[j][c] += 1 def dfs(i, j): if i == n: return 1 if j == m: return 0 return (dfs(i, j+1) + dfs(i+1, j+1) * d[j][target[i]]) % int(1e9 + 7) return dfs(0, 0) words = ["pqqp","qppq"] target = "qpq" print(solve(words, target))
입력
"95643", "45963"
출력
4