사전이 주어지면 대상 문자열을 형성하는 방법의 수

1639. 사전이 주어지면 대상 문자열을 형성하는 방법의 수

난이도:어려움

주제: 배열, 문자열, 동적 프로그래밍

같은 길이 단어의 문자열 목록과 문자열 대상이 제공됩니다.

당신의 임무는 다음 규칙에 따라 주어진 단어를 사용하여 타겟을 형성하는 것입니다.

• 타겟은 왼쪽에서 오른쪽으로 형성되어야 합니다.
• 대상의 i^번째 문자(0-색인)를 구성하려면 j^{번째번째 문자를 선택할 수 있습니다. 🎜> target[i] = 단어[j][k]인 경우 단어로 된 문자열.}
j
• 번째 ^{단어 문자열에서 k}번째 ^{문자를 사용하면 x}번째를 더 이상 사용할 수 없습니다^{. x}
문자열 타겟이 형성될 때까지 이 과정을 반복하세요.

주의 위의 조건이 충족되면 단어에서 동일 문자열의 여러 문자를 사용할 수 있습니다.

단어에서 대상을 형성하는 방법의 수를 반환합니다. 답이 너무 클 수 있으므로 모듈로 109 ^{7로 반환하세요.}

예 1:

• 입력: 단어 = ["acca","bbbb","caca"], 대상 = "aba"
• 출력: 6
• 설명: 타겟을 형성하는 방법에는 6가지가 있습니다.
  "아바" -> 인덱스 0("acca"), 인덱스 1("bbbb"), 인덱스 3("caca")
  "아바" -> 인덱스 0("acca"), 인덱스 2("bbbb"), 인덱스 3("caca")
  "아바" -> 인덱스 0("acca"), 인덱스 1("bbbb"), 인덱스 3("acca")
  "아바" -> 인덱스 0("acca"), 인덱스 2("bbbb"), 인덱스 3("acca")
  "아바" -> 인덱스 1("caca"), 인덱스 2("bbbb"), 인덱스 3("acca")
  "아바" -> 인덱스 1("caca"), 인덱스 2("bbbb"), 인덱스 3("caca")

예 2:

• 입력: 단어 = ["abba","baab"], 대상 = "bab"
• 출력: 4
• 설명: 타겟을 형성하는 방법에는 4가지가 있습니다.
  "밥" -> 인덱스 0("baab"), 인덱스 1("baab"), 인덱스 2("abba")
  "밥" -> 인덱스 0("baab"), 인덱스 1("baab"), 인덱스 3("baab")
  "밥" -> 인덱스 0("baab"), 인덱스 2("baab"), 인덱스 3("baab")
  "밥" -> 인덱스 1("abba"), 인덱스 2("baab"), 인덱스 3("baab")

제약조건:

• 1
• 1
• 단어에 포함된 모든 문자열의 길이는 동일합니다.
• 1
• word[i] 및 target에는 영문 소문자만 포함됩니다.

힌트:

1. 각 인덱스 i에 대해 i^번째 행에 각 문자의 빈도를 저장합니다.
2. 동적 프로그래밍을 이용하여 주파수 배열을 이용하여 목표 문자열을 얻는 방법의 수를 계산해 보세요.

해결책:

이 문제는 문자 사용에 대한 특정 규칙에 따라 단어 사전에서 대상 문자열을 형성하는 방법의 수를 찾는 것입니다. 이는 동적 프로그래밍(DP)과 문자 빈도 전처리

를 사용하여 효율적으로 풀 수 있는 조합 문제입니다.

핵심사항

1. 제약조건:
   • 단어의 길이가 같습니다.
   • 단어 문자는 왼쪽에서 오른쪽으로만 사용할 수 있습니다.
2. 도전:
   • 큰 제약으로 인해 타겟 형성 방법을 효율적으로 계산합니다.
   • 메모이제이션으로 재계산을 방지하세요.
3. 모듈로:
   • 결과가 클 수 있으므로 모든 계산은 모듈로 10⁹ 7로 수행됩니다.

접근방법

솔루션은 다음을 사용합니다.

1. 전처리:
   • 모든 단어의 모든 위치에서 각 문자의 빈도를 계산합니다.
2. 동적 프로그래밍:
   • 2D DP 테이블을 사용하여 대상 문자열을 구성하는 방법의 수를 계산합니다.

단계:

1. 단어를 빈도 배열(개수)로 전처리합니다.
2. 전처리된 개수를 사용하여 타겟을 형성하는 방법의 수를 반복적으로 찾는 DP 함수를 정의합니다.

계획

1. 입력 구문 분석:
   • 단어와 대상을 받아들입니다.
2. 전처리:
   • counts[j][char]가 모든 단어에서 j 위치의 char 빈도를 나타내는 counts 배열을 만듭니다.
3. 동적 프로그래밍:
   • 메모이제이션과 함께 재귀 함수를 사용하여 단어의 유효한 위치에 있는 문자를 사용하여 타겟을 형성하는 방법의 수를 계산합니다.
4. 결과 반환:
   • 총 개수를 모듈로 10으로 반환⁹ 7.

PHP에서 이 솔루션을 구현해 보겠습니다. 1639. 사전이 주어지면 대상 문자열을 형성하는 방법의 수

<?php const MOD = 1000000007;
/**
 * @param String[] $words
 * @param String $target
 * @return Integer
 */
function numWays($words, $target) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function for DP
 *
 * @param $i
 * @param $j
 * @param $counts
 * @param $target
 * @param $memo
 * @return float|int|mixed
 */
private function dp($i, $j, $counts, $target, &$memo) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Usage
$words = ["acca", "bbbb", "caca"];
$target = "aba";
echo numWays($words, $target) . "\n"; // Output: 6

$words = ["abba", "baab"];
$target = "bab";
echo numWays($words, $target) . "\n"; // Output: 4
?>

설명:

1. 전처리 단계:

   • 개수 배열 구축:
     • 단어의 각 열에 대해 각 문자의 발생 횟수를 셉니다.
   • 예: 단어 = ["acca", "bbbb", "caca"]인 경우 첫 번째 열에 대해 counts[0] = {'a': 1, 'b': 1, 'c': 1 }.

2. 재귀 DP:

   • dp(i, j) 정의:
     • i는 타겟의 현재 인덱스입니다.
     • j는 단어로 표현된 현재 위치입니다.
   • 기본 사례:
     • i == len(target)인 경우: 전체 대상이 형성됨 → 1을 반환합니다.
     • j == len(words[0])인 경우: 더 이상 사용할 열이 없으며 → 0을 반환합니다.
   • 반복:
     • 옵션 1: j 위치의 counts[j][target[i]] 문자를 사용합니다.
     • 옵션 2: 위치 j를 건너뜁니다.

3. 최적화:

   • 메모이제이션 테이블을 사용해 중복된 하위 문제의 결과를 저장하세요.

예시 연습

입력:

단어 = ["acca", "bbbb", "caca"], 대상 = "aba"

1. 전처리:

   • 개수[0] = {'a': 2, 'b': 0, 'c': 1}
   • 개수[1] = {'a': 0, 'b': 3, 'c': 0}
   • 개수[2] = {'a': 1, 'b': 0, 'c': 2}
   • 개수[3] = {'a': 2, 'b': 0, 'c': 1}

2. DP 계산:

   • dp(0, 0): 0열부터 시작하여 "aba"를 형성하는 방법의 수.
   • 카운트 사용과 열 건너뛰기를 결합하여 재귀적으로 계산합니다.

출력: 6

시간복잡도

1. 전처리: O(n x m), 여기서 n은 단어 수이고 m은 단어 길이입니다.
2. 동적 프로그래밍: O(l x m), 여기서 l은 대상의 길이입니다.
3. 합계: O(n x m l x m).

예시 출력

• 입력: 단어 = ["acca", "bbbb", "caca"], 대상 = "aba"
• 출력: 6

이 문제는 조합 문제를 효율적으로 해결하기 위해 전처리와 동적 프로그래밍을 결합한 훌륭한 예입니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 사전이 주어지면 대상 문자열을 형성하는 방법의 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!