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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

종종 키워드와 추적 매개 변수로 혼란스러워하는 긴 URL은 방문자를 방해 할 수 있습니다. URL 단축 스크립트는 솔루션을 제공하여 소셜 미디어 및 기타 플랫폼에 이상적인 간결한 링크를 만듭니다. 이 스크립트는 개별 웹 사이트 a에 유용합니다

Instagram은 2012 년 Facebook에서 유명한 인수에 이어 타사 사용을 위해 두 개의 API 세트를 채택했습니다. Instagram Graph API 및 Instagram Basic Display API입니다. 개발자는

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

이것은 Laravel 백엔드가있는 React Application을 구축하는 데있어 시리즈의 두 번째이자 마지막 부분입니다. 이 시리즈의 첫 번째 부분에서는 기본 제품 목록 응용 프로그램을 위해 Laravel을 사용하여 편안한 API를 만들었습니다. 이 튜토리얼에서는 Dev가 될 것입니다

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

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

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

2025 PHP Landscape Survey는 현재 PHP 개발 동향을 조사합니다. 개발자와 비즈니스에 대한 통찰력을 제공하는 프레임 워크 사용, 배포 방법 및 과제를 탐색합니다. 이 조사는 현대 PHP Versio의 성장을 예상합니다


핫 AI 도구

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

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

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

Clothoff.io
AI 옷 제거제

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

인기 기사

뜨거운 도구

드림위버 CS6
시각적 웹 개발 도구

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

Eclipse용 SAP NetWeaver 서버 어댑터
Eclipse를 SAP NetWeaver 애플리케이션 서버와 통합합니다.

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

Atom Editor Mac 버전 다운로드
가장 인기 있는 오픈 소스 편집기
