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

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 <= 단어.길이 <= 1000
• 1 <= 단어[i].length <= 1000
• 단어에 포함된 모든 문자열의 길이는 동일합니다.
• 1 <= target.length <= 1000
• 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. 사전이 주어지면 대상 문자열을 형성하는 방법의 수

  
  
  설명:




전처리 단계:

개수 배열 구축:


단어의 각 열에 대해 각 문자의 발생 횟수를 셉니다.


예: 단어 = ["acca", "bbbb", "caca"]인 경우 첫 번째 열에 대해 counts[0] = {'a': 1, 'b': 1, 'c': 1 }.



재귀 DP:


dp(i, j) 정의:



i는 타겟의 현재 인덱스입니다.

j는 단어로 표현된 현재 위치입니다.


기본 사례:


i == len(target)인 경우: 전체 대상이 형성됨 → 1을 반환합니다.
j == len(words[0])인 경우: 더 이상 사용할 열이 없으며 → 0을 반환합니다.


반복:


옵션 1: j 위치의 counts[j][target[i]] 문자를 사용합니다.
옵션 2: 위치 j를 건너뜁니다.





최적화:


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





  
  
  예시 연습


입력:


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



전처리:


개수[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}



DP 계산:



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




출력: 6


  
  
  시간복잡도




전처리: O(n x m), 여기서 n은 단어 수이고 m은 단어 길이입니다.

동적 프로그래밍: O(l x m), 여기서 l은 대상의 길이입니다.

합계: O(n x m l x m).



  
  
  예시 출력




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


출력: 6



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

연락처 링크

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

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


링크드인
깃허브



          

            
  

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