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
- 1
- 1
- Dictionary[i]와 s는 영어 소문자로만 구성됩니다
- 사전에 고유한 단어가 포함되어 있습니다
힌트:
- 여기서 동적 프로그래밍을 사용할 수 있나요?
- s[0:i]를 최적으로 분리하려면 DP[i]를 최소 추가 문자로 정의하세요.
해결책:
dp[i]가 최적 분할 후 하위 문자열 s[0:i]에 있는 추가 문자의 최소 수를 나타내는 dp 배열을 정의할 수 있습니다.
접근하다:
-
동적 프로그래밍 정의:
- dp[i]를 하위 문자열 s[0:i]에 있는 추가 문자의 최소 개수로 설정합니다.
- dp[i]를 계산하려면 다음을 수행할 수 있습니다.
- s[i-1] 문자를 추가 문자로 간주하고 다음 인덱스로 이동하세요.
- 또는 인덱스 i로 끝나는 하위 문자열이 사전에 있는지 확인하고, 그렇다면 이를 사용하여 추가 문자를 줄이세요.
-
전환:
- 각 인덱스 i에 대해 다음 중 하나를 수행합니다.
- s[i]를 추가 문자로 처리하는 경우 dp[i-1]에 1을 추가합니다.
- 가능한 모든 하위 문자열 s[j:i](j
- 각 인덱스 i에 대해 다음 중 하나를 수행합니다.
-
결과:
- dp[len(s)] 값은 전체 문자열 s의 최소 추가 문자 수를 제공합니다.
이 솔루션을 PHP로 구현해 보겠습니다: 2707. 문자열의 추가 문자
<?php /** * @param String $s * @param String[] $dictionary * @return Integer */ function minExtraChar($s, $dictionary) { ... ... ... /** * go to ./solution.php */ } // Test cases echo minExtraChar("leetscode", ["leet","code","leetcode"]); // Output: 1 echo "\n"; echo minExtraChar("sayhelloworld", ["hello","world"]); // Output: 3 ?>
설명:
-
기본 사례:
- 빈 문자열에는 추가 문자가 없으므로 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

Laravel은 직관적 인 플래시 방법을 사용하여 임시 세션 데이터 처리를 단순화합니다. 응용 프로그램에 간단한 메시지, 경고 또는 알림을 표시하는 데 적합합니다. 데이터는 기본적으로 후속 요청에만 지속됩니다. $ 요청-

PHP 클라이언트 URL (CURL) 확장자는 개발자를위한 강력한 도구이며 원격 서버 및 REST API와의 원활한 상호 작용을 가능하게합니다. PHP CURL은 존경받는 다중 프로모토콜 파일 전송 라이브러리 인 Libcurl을 활용하여 효율적인 execu를 용이하게합니다.

PHP 로깅은 웹 애플리케이션을 모니터링하고 디버깅하고 중요한 이벤트, 오류 및 런타임 동작을 캡처하는 데 필수적입니다. 시스템 성능에 대한 귀중한 통찰력을 제공하고 문제를 식별하며 더 빠른 문제 해결을 지원합니다.

Laravel은 간결한 HTTP 응답 시뮬레이션 구문을 제공하여 HTTP 상호 작용 테스트를 단순화합니다. 이 접근법은 테스트 시뮬레이션을보다 직관적으로 만들면서 코드 중복성을 크게 줄입니다. 기본 구현은 다양한 응답 유형 단축키를 제공합니다. Illuminate \ support \ Facades \ http를 사용하십시오. http :: 가짜 ([ 'google.com'=> 'Hello World', 'github.com'=> [ 'foo'=> 'bar'], 'forge.laravel.com'=>

고객의 가장 긴급한 문제에 실시간 인스턴트 솔루션을 제공하고 싶습니까? 라이브 채팅을 통해 고객과 실시간 대화를 나누고 문제를 즉시 해결할 수 있습니다. 그것은 당신이 당신의 관습에 더 빠른 서비스를 제공 할 수 있도록합니다.

기사는 PHP 5.3에 도입 된 PHP의 LSB (Late STATIC BING)에 대해 논의하여 정적 방법의 런타임 해상도가보다 유연한 상속을 요구할 수있게한다. LSB의 실제 응용 프로그램 및 잠재적 성능

이 기사에서는 프레임 워크에 사용자 정의 기능 추가, 아키텍처 이해, 확장 지점 식별 및 통합 및 디버깅을위한 모범 사례에 중점을 둡니다.

Alipay PHP ...


핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

AI Hentai Generator
AI Hentai를 무료로 생성하십시오.

인기 기사

뜨거운 도구

mPDF
mPDF는 UTF-8로 인코딩된 HTML에서 PDF 파일을 생성할 수 있는 PHP 라이브러리입니다. 원저자인 Ian Back은 자신의 웹 사이트에서 "즉시" PDF 파일을 출력하고 다양한 언어를 처리하기 위해 mPDF를 작성했습니다. HTML2FPDF와 같은 원본 스크립트보다 유니코드 글꼴을 사용할 때 속도가 느리고 더 큰 파일을 생성하지만 CSS 스타일 등을 지원하고 많은 개선 사항이 있습니다. RTL(아랍어, 히브리어), CJK(중국어, 일본어, 한국어)를 포함한 거의 모든 언어를 지원합니다. 중첩된 블록 수준 요소(예: P, DIV)를 지원합니다.

SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.

Dreamweaver Mac版
시각적 웹 개발 도구

에디트플러스 중국어 크랙 버전
작은 크기, 구문 강조, 코드 프롬프트 기능을 지원하지 않음

안전한 시험 브라우저
안전한 시험 브라우저는 온라인 시험을 안전하게 치르기 위한 보안 브라우저 환경입니다. 이 소프트웨어는 모든 컴퓨터를 안전한 워크스테이션으로 바꿔줍니다. 이는 모든 유틸리티에 대한 액세스를 제어하고 학생들이 승인되지 않은 리소스를 사용하는 것을 방지합니다.
