고유한 길이의 유사 부분 수열

1930년. 고유 길이-3 회문 부분 시퀀스

난이도:중

주제: 해시 테이블, 문자열, 비트 조작, 접두사 합계

문자열 s가 주어지면 s의 하위 시퀀스인 길이가 3인 고유 회문의 개수를 반환합니다.

참고 동일한 하위 시퀀스를 얻는 방법이 여러 개 있더라도 여전히 한 번만 계산됩니다.

회문은 앞으로 읽어도 뒤로 읽어도 같은 문자열입니다.

문자열의 하위 시퀀스는 나머지 문자의 상대적 순서를 변경하지 않고 일부 문자가 삭제된(없음일 수 없음) 원래 문자열에서 생성된 새 문자열입니다.

• 예를 들어 'ace'는 'abcde'의 하위 수열입니다.

예 1:

• 입력: s = "aabca"
• 출력: 3
• 설명: 길이가 3인 회문 부분 수열 3개는 다음과 같습니다.
  • "aba"("aabca"의 후속)
  • "aaa"("aabca"의 후속)
  • "aca"("aabca"의 후속)

예 2:

• 입력: s = "adc"
• 출력: 0
• 설명: "adc"에는 길이가 3인 회문 부분 수열이 없습니다.

예 3:

• 입력: s = "bbcbaba"
• 출력: 4
• 설명: 길이가 3인 회문 부분 수열 4개는 다음과 같습니다.
  • "bbb"("bbcbaba"의 후속)
  • "bcb"("bbcbaba"의 후속)
  • "bab"("bbcbaba"의 후속)
  • "aba"("bbcbaba"의 후속)

제약조건:

• 3 5
• s는 영문 소문자로만 구성됩니다.

힌트:

1. 길이 3개의 회문 문자열의 최대 개수는 몇 개입니까?
2. 특정 위치의 왼쪽에 나타나는 문자를 어떻게 추적할 수 있나요?

해결책:

접두사 및 접미사 문자 추적을 활용하여 모든 유효한 회문 하위 시퀀스를 계산하는 효율적인 알고리즘을 사용할 수 있습니다.

접근하다

1. 접두사 문자 추적:
   배열을 사용하여 문자열의 각 위치 왼쪽에 있는 문자 집합을 저장합니다. 이는 문자가 회문 하위 시퀀스의 첫 번째 부분을 형성할 수 있는지 효율적으로 확인하는 데 도움이 됩니다.

2. 접미사 문자 추적:
   다른 배열을 사용하여 문자열의 각 위치 오른쪽에 있는 문자 집합을 저장합니다. 이는 문자가 회문 하위 시퀀스의 세 번째 부분을 형성할 수 있는지 효율적으로 확인하는 데 도움이 됩니다.

3. 회문 하위 시퀀스 계산:
   문자열의 각 문자에 대해 길이가 3인 회문의 중간 문자로 간주합니다. 고유한 회문을 결정하려면 접두사와 접미사의 유효한 조합을 모두 확인하세요.

4. 스토어 결과:
   해시 세트를 사용하여 중복이 없도록 고유한 회문 하위 시퀀스를 저장하세요.

이 솔루션을 PHP로 구현해 보겠습니다: 1930. 고유 길이-3 회문 부분 시퀀스

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

// Test cases
echo countPalindromicSubsequence("aabca") . PHP_EOL; // Output: 3
echo countPalindromicSubsequence("adc") . PHP_EOL;   // Output: 0
echo countPalindromicSubsequence("bbcbaba") . PHP_EOL; // Output: 4
?>

설명:

1. 접두사 배열:

   • i 위치의 각 문자에 대해 prefix[i]는 인덱스 i 앞에 있는 모든 고유 문자를 저장합니다.

2. 접미사 배열:

   • i 위치의 각 문자에 대해 suffix[i]는 인덱스 i 다음에 나오는 모든 고유 문자를 저장합니다.

3. 중간 문자:

   • 각 캐릭터를 회문의 중앙으로 생각하세요. 중간 문자와 일치하는 각 접두사와 접미사 문자의 조합에 대해 길이가 3인 회문을 형성합니다.

4. 해시 맵:

   • 연관 배열($uniquePalindromes)을 사용하여 고유한 회문을 저장하면 중복 항목이 계산되지 않습니다.

복잡성

• 시간 복잡도: O(n)

  • 문자열을 두 번 탐색하여 접두사 및 접미사 배열을 계산합니다.
  • 세 번째 순회에서는 유효한 회문 하위 시퀀스를 확인합니다.

• 공간 복잡도: O(n)

  • 접두사 및 접미사 배열의 경우

산출

코드는 주어진 예에 대해 올바른 결과를 생성합니다.

• 입력: "aabca" → 출력: 3
• 입력: "adc" → 출력: 0
• 입력: "bbcbaba" → 출력: 4

연락처 링크

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

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

• 링크드인
• 깃허브

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