문자열의 추가 문자

2707. 문자열의 추가 문자

난이도:중

주제: 배열, 해시 테이블, 문자열, 동적 프로그래밍, Trie

인덱스가 0인 문자열과 단어 사전이 제공됩니다. 각 하위 문자열이 사전에 존재하도록 s를 하나 이상의 겹치지 않는 하위 문자열로 나누어야 합니다. 하위 문자열에는 없는 s의 추가 문자가 있을 수 있습니다.

이별 시 남은 추가 문자 수최소를 최적으로반환합니다.

예 1:

• 입력: s = "leetscode", 사전 = ["leet","code","leetcode"]
• 출력: 1
• 설명: s를 두 개의 하위 문자열로 나눌 수 있습니다: 인덱스 0에서 3까지의 "leet"와 인덱스 5에서 8까지의 "code". 사용되지 않은 문자가 1개(인덱스 4에) 있으므로 1을 반환합니다. .

예 2:

• 입력: s = "sayhelloworld", Dictionary = ["hello","world"]
• 출력: 3
• 설명: s를 두 개의 하위 문자열로 나눌 수 있습니다. 인덱스 3~7의 "hello"와 인덱스 8~12의 "world"입니다. 인덱스 0, 1, 2의 문자는 어떤 하위 문자열에도 사용되지 않으며 따라서 추가 문자로 간주됩니다. 따라서 3을 반환합니다.

제약조건:

• 1 <= s.length <= 50
• 1 <= 사전.길이 <= 50
• 1 <= 사전[i].length <= 50
• Dictionary[i]와 s는 영어 소문자로만 구성됩니다
• 사전에 고유한 단어가 포함되어 있습니다

힌트:

1. 여기서 동적 프로그래밍을 사용할 수 있나요?
2. s[0:i]를 최적으로 분리하려면 DP[i]를 최소 추가 문자로 정의하세요.

해결책:

dp[i]가 최적 분할 후 하위 문자열 s[0:i]에 있는 추가 문자의 최소 수를 나타내는 dp 배열을 정의할 수 있습니다.

접근하다:

1. 동적 프로그래밍 정의:

   • dp[i]를 하위 문자열 s[0:i]에 있는 추가 문자의 최소 개수로 설정합니다.
   • dp[i]를 계산하려면 다음을 수행할 수 있습니다.
     • s[i-1] 문자를 추가 문자로 간주하고 다음 인덱스로 이동하세요.
     • 또는 인덱스 i로 끝나는 하위 문자열이 사전에 있는지 확인하고, 그렇다면 이를 사용하여 추가 문자를 줄이세요.

2. 전환:

   • 각 인덱스 i에 대해 다음 중 하나를 수행합니다.
     • s[i]를 추가 문자로 처리하는 경우 dp[i-1]에 1을 추가합니다.
     • 가능한 모든 하위 문자열 s[j:i](j < i의 경우)를 확인하고 s[j:i]가 사전에 있으면 dp[j]를 기반으로 dp[i]를 업데이트합니다.

3. 결과:

   • dp[len(s)] 값은 전체 문자열 s의 최소 추가 문자 수를 제공합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2707. 문자열의 추가 문자

  
  
  설명:




기본 사례:



빈 문자열에는 추가 문자가 없으므로 dp[0] = 0입니다.



사전 조회:


상시 조회를 위해 array_flip()을 사용하여 사전 단어를 해시 맵에 저장합니다.



전환:


각 위치 i에 대해 가능한 모든 하위 문자열 s[j:i]를 확인합니다. 사전에 하위 문자열이 있으면 dp[i] 값을 업데이트합니다.



시간 복잡도:


시간 복잡도는 O(n^2)입니다. 여기서 n은 문자열 s의 길이입니다. 왜냐하면 각 인덱스에 대해 이전의 모든 인덱스를 확인하여 하위 문자열을 형성하기 때문입니다.





  
  
  테스트 결과:


사전 ["leet","code","leetcode"]가 있는 입력 "leetscode"의 경우 함수는 1개의 추가 문자("s")만 남으므로 1을 올바르게 반환합니다.

사전 ["hello","world"]가 있는 입력 "sayhelloworld"의 경우 처음 세 문자("say")가 추가이므로 함수는 3을 반환합니다.

연락처 링크

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

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


링크드인
깃허브



          

            
  

            
        
위 내용은 문자열의 추가 문자의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!