찾다
백엔드 개발PHP 튜토리얼문자열의 추가 문자

Extra Characters in a String

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는 영어 소문자로만 구성됩니다
  • 사전에 고유한 단어가 포함되어 있습니다

힌트:

  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
  3. 결과:

    • 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
?>

설명:

  1. 기본 사례:

    • 빈 문자열에는 추가 문자가 없으므로 dp[0] = 0입니다.
  2. 사전 조회:

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

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

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

테스트 결과:

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

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

연락처 링크

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

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

  • 링크드인
  • 깃허브

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

성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
Laravel의 플래시 세션 데이터로 작업합니다Laravel의 플래시 세션 데이터로 작업합니다Mar 12, 2025 pm 05:08 PM

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

PHP의 컬 : REST API에서 PHP Curl Extension 사용 방법PHP의 컬 : REST API에서 PHP Curl Extension 사용 방법Mar 14, 2025 am 11:42 AM

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

PHP 로깅 : PHP 로그 분석을위한 모범 사례PHP 로깅 : PHP 로그 분석을위한 모범 사례Mar 10, 2025 pm 02:32 PM

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

Laravel 테스트에서 단순화 된 HTTP 응답 조롱Laravel 테스트에서 단순화 된 HTTP 응답 조롱Mar 12, 2025 pm 05:09 PM

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

Codecanyon에서 12 개의 최고의 PHP 채팅 스크립트Codecanyon에서 12 개의 최고의 PHP 채팅 스크립트Mar 13, 2025 pm 12:08 PM

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

PHP에서 늦은 정적 결합의 개념을 설명하십시오.PHP에서 늦은 정적 결합의 개념을 설명하십시오.Mar 21, 2025 pm 01:33 PM

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

프레임 워크 사용자 정의/확장 : 사용자 정의 기능을 추가하는 방법.프레임 워크 사용자 정의/확장 : 사용자 정의 기능을 추가하는 방법.Mar 28, 2025 pm 05:12 PM

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

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

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

뜨거운 도구

mPDF

mPDF

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

SublimeText3 중국어 버전

SublimeText3 중국어 버전

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

Dreamweaver Mac版

Dreamweaver Mac版

시각적 웹 개발 도구

에디트플러스 중국어 크랙 버전

에디트플러스 중국어 크랙 버전

작은 크기, 구문 강조, 코드 프롬프트 기능을 지원하지 않음

안전한 시험 브라우저

안전한 시험 브라우저

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