문자열을 최대 고유 하위 문자열 수로 분할

1593. 문자열을 최대 고유 하위 문자열 수로 분할

난이도:중

주제: 해시 테이블, 문자열, 역추적

문자열 s가 주어지면 주어진 문자열을 분할할 수 있는 고유 하위 문자열의 최대 개수를 반환합니다.

문자열 s를 비어 있지 않은 하위 문자열 목록으로 분할할 수 있습니다. 여기서 하위 문자열을 연결하면 원래 문자열이 형성됩니다. 그러나 하위 문자열을 모두 고유하도록 분할해야 합니다.

하위 문자열은 문자열 내의 연속된 문자 시퀀스입니다.

예 1:

• 입력: s = "ababccc"
• 출력: 5
• 설명: 최대로 분할하는 한 가지 방법은 ['a', 'b', 'ab', 'c', 'cc']입니다. 'a', 'b', 'a', 'b', 'c', 'cc']와 같이 나누는 것은 'a'와 'b'가 여러 번 있으므로 유효하지 않습니다.

예 2:

• 입력: s = "aba"
• 출력: 2
• 설명: 최대로 분할하는 한 가지 방법은 ['a', 'ba']입니다.

예 3:

• 입력: s = "aa"
• 출력: 1
• 설명: 더 이상 문자열을 분할하는 것은 불가능합니다.

제약조건:

• 1
• s에는 영문 소문자만 포함됩니다.

힌트:

1. 세트를 사용하여 이미 사용된 하위 문자열을 추적하세요
2. 모든 위치에서 가능한 각 하위 문자열을 시도하고 완전한 분할이 불가능할 경우 역추적

해결책:

역추적 접근 방식을 사용할 수 있습니다. 여기에는 문자열의 현재 위치에서 부분 문자열을 재귀적으로 생성하고 지금까지 사용한 고유한 부분 문자열을 추적하는 작업이 포함됩니다.

다음은 단계별 해결 방법입니다.

1. 재귀 함수: 문자열의 현재 인덱스부터 시작하여 가능한 모든 하위 문자열을 탐색하는 함수를 만듭니다.
2. 고유성을 위한 설정: 현재 재귀 경로에 사용된 고유한 하위 문자열을 추적하려면 집합(또는 PHP의 배열)을 사용하세요.
3. 역추적: 하위 문자열이 선택되면 계속해서 다음 하위 문자열을 선택할 수 있습니다. 반복하지 않고는 더 이상 하위 문자열을 형성할 수 없는 지점에 도달하면 되돌아갑니다.
4. 기본 사례: 문자열 끝에 도달하면 형성된 고유한 하위 문자열의 수를 셉니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 1593. 문자열을 최대 고유 하위 문자열 수로 분할

<?php
class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function maxUniqueSplit($s) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $s
     * @param $used
     * @param $start
     * @return int|mixed
     */
    private function backtrack($s, $used, $start) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage
$solution = new Solution();
echo $solution->maxUniqueSplit("ababccc"); // Output: 5
echo "\n";
echo $solution->maxUniqueSplit("aba"); // Output: 2
echo "\n";
echo $solution->maxUniqueSplit("aa"); // Output: 1
?>

설명:

1. 함수 서명: 주요 함수는 역추적 프로세스를 초기화하는 maxUniqueSplit입니다.

2. 역추적:

   • 역추적 기능은 문자열, 사용된 하위 문자열 배열 및 현재 시작 인덱스를 사용합니다.
   • 시작 인덱스가 문자열의 끝에 도달하면 수집된 고유 하위 문자열의 개수를 반환합니다.
   • 루프는 가능한 끝 인덱스를 반복하여 시작 인덱스에서 하위 문자열을 생성합니다.
   • 부분 문자열이 고유한 경우(사용된 배열에 아직 없음) 해당 항목이 사용된 배열에 추가되고 함수는 다음 인덱스에 대해 반복됩니다.
   • 해당 경로를 탐색한 후 하위 문자열을 제거하여 역추적하고 다른 가능성을 탐색합니다.

3. 출력: 이 함수는 다양한 입력 문자열에 대한 고유 하위 문자열의 최대 수를 반환합니다.

복잡성

• 역추적 특성으로 인해 특히 긴 문자열의 경우 시간 복잡도가 높을 수 있지만 제약 조건(최대 길이 16)을 고려하면 이 솔루션은 입력 제한에 대해 충분히 효율적입니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 문자열을 최대 고유 하위 문자열 수로 분할의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!