K 회문 문자열 생성-PHP 튜토리얼-php.cn

K 회문 문자열 생성

Linda Hamilton

풀어 주다： 2025-01-11 22:07:44

원래의

733명이 탐색했습니다.

Construct K Palindrome Strings

1400. K 회문 문자열 구성

난이도:중

주제: 해시 테이블, 문자열, 탐욕, 계산

문자열 s와 정수 k가 주어지면 s의 모든 문자를 사용하여 k 회문 문자열을 구성할 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

예 1:

입력: s = "annabelle", k = 2
출력: true
설명: s의 모든 문자를 사용하여 두 개의 회문을 구성할 수 있습니다.
- 가능한 구문 "anna" "elble", "anbna" "elle", "anellena" "b"

예 2:

입력: s = "leetcode", k = 3
출력: false
설명: s의 모든 문자를 사용하여 3개의 회문을 구성하는 것은 불가능합니다.

예 3:

입력: s = "true", k = 4
출력: true
설명: 유일한 해결 방법은 각 문자를 별도의 문자열에 넣는 것입니다.

제약조건:

1 5
s는 영문 소문자로 구성됩니다.
1 5

힌트:

s.length < k 우리는 s에서 k 문자열을 구성할 수 없으며 대답은 거짓입니다.
홀수 개수의 문자 수가 > k이면 우리가 구성할 수 있는 회문 문자열의 최소 개수는 > k이고 대답은 거짓입니다.
그렇지 않으면 정확히 k 개의 회문 문자열을 구성할 수 있으며 대답은 참입니다(왜?).

해결책:

다음 사항을 고려해야 합니다.

주요 관찰:

회문 특성:
- 회문은 앞으로 읽어도 뒤로 읽어도 같은 문자열입니다.
- 짝수 길이의 회문의 경우 모든 문자가 짝수 번 나타나야 합니다.
- 홀수 길이의 회문의 경우 하나를 제외한 모든 문자가 짝수 번 나타나야 합니다(홀수 번 나타나는 문자가 중앙에 표시됩니다).
필요조건:
- s의 길이가 k보다 작으면 k개의 문자열을 구성하는 것이 불가능하므로 false를 반환합니다.
- k개의 회문을 형성하려면 홀수 번 나타나는 문자의 총 개수가 최대 k개여야 합니다. 이는 각 회문이 홀수 개수의 문자(홀수 길이 회문의 중심 문자)를 최대 1개까지 가질 수 있기 때문입니다.

접근하다:

문자열에서 각 문자의 빈도를 계산합니다.
홀수 빈도의 문자가 몇 개인지 세어보세요.
홀수 주파수의 개수가 k를 초과하면 false를 반환합니다(k개의 회문을 형성하는 것이 불가능하기 때문입니다).

이 솔루션을 PHP: 1400으로 구현해 보겠습니다. K 회문 문자열 생성

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

// Test cases
var_dump(canConstruct("annabelle", 2)); // Output: true
var_dump(canConstruct("leetcode", 3)); // Output: false
var_dump(canConstruct("true", 4));      // Output: true
?>

로그인 후 복사

설명:

빈도수: 연관 배열 $freq를 사용하여 문자열에서 각 문자의 발생 횟수를 계산합니다.
홀수 개수: 홀수 문자가 몇 개나 나오는지 확인합니다. 이는 회문을 형성할 수 있는지 결정하는 데 도움이 됩니다.
조건 확인: 홀수 빈도의 문자 수가 k보다 크면 k개의 회문을 형성하는 것이 불가능하므로 false를 반환합니다. 그렇지 않으면 true를 반환합니다.