접두사 및 접미사 쌍 계산 I

3042. 접두사와 접미사 쌍 계산 I

난이도: 쉬움

주제: 배열, 문자열, Trie, 롤링 해시, 문자열 일치, 해시 함수

인덱스가 0인 문자열 배열 단어가 주어졌습니다.

두 개의 문자열 str1과 str2를 사용하는 부울 함수 isPrefixAndSuffix를 정의해 보겠습니다.

• isPrefixAndSuffix(str1, str2)는 str1이 str2의 접두사1 및 접미사²인 경우 true를 반환하고, 그렇지 않은 경우 false를 반환합니다.
예를 들어, isPrefixAndSuffix("aba", "ababa")는 "aba"가 "ababa"의 접두사이자 접미사이므로 true이지만 isPrefixAndSuffix("abc", "abcd")는 false입니다.

i 번호

를 나타내는 정수를 반환합니다. j, isPrefixAndSuffix(words[i], word[j])는 true입니다.

예 1:

입력:
• 단어 = ["a","aba","ababa","aa"]
출력:
• 4
설명:
• 이 예에서 계산된 인덱스 쌍은 다음과 같습니다. i = 0이고 j = 1입니다. isPrefixAndSuffix("a", "aba")가 true이기 때문입니다. i = 0이고 j = 2입니다. isPrefixAndSuffix("a", "ababa")가 true이기 때문입니다. i = 0이고 j = 3입니다. isPrefixAndSuffix("a", "aa")가 true이기 때문입니다. i = 1이고 j = 2입니다. isPrefixAndSuffix("aba", "ababa")가 true이기 때문입니다. 그러므로 답은 4이다.

예 2:

입력:
• 단어 = ["pa","papa","ma","mama"]
출력:
• 2
설명:
• 이 예에서 계산된 인덱스 쌍은 다음과 같습니다. i = 0이고 j = 1입니다. isPrefixAndSuffix("pa", "papa")가 true이기 때문입니다. i = 2이고 j = 3입니다. isPrefixAndSuffix("ma", "mama")가 true이기 때문입니다. 따라서 답은 2입니다.

예 3:

입력:
• 단어 = ["abab","ab"]
출력:
• 0
설명:
• 이 예에서 유일한 유효한 인덱스 쌍은 i = 0 및 j = 1이고 isPrefixAndSuffix("abab", "ab")는 false입니다. 그러므로 답은 0이다.

제약조건:

1

1

word[i]는 영문 소문자로만 구성됩니다.

힌트:

모든 인덱스 쌍(i, j)을 반복하여 i

답은 isPrefixAndSuffix(words[i],words[j]) == true인 총 쌍 수입니다.

해결책:

i

이 솔루션을 PHP로 구현해 보겠습니다: 3042. 접두사와 접미사 쌍 계산 I

<?php /**
 * @param String[] $words
 * @return Integer
 */
function countPrefixAndSuffixPairs($words) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to check if str1 is both a prefix and a suffix of str2
 *
 * @param $str1
 * @param $str2
 * @return bool
 */
function isPrefixAndSuffix($str1, $str2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Test Cases
$words1 = ["a", "aba", "ababa", "aa"];
$words2 = ["pa", "papa", "ma", "mama"];
$words3 = ["abab", "ab"];

echo countPrefixAndSuffixPairs($words1) . "\n";  // Output: 4
echo countPrefixAndSuffixPairs($words2) . "\n";  // Output: 2
echo countPrefixAndSuffixPairs($words3) . "\n";  // Output: 0
?>

설명:

1. countPrefixAndSuffixPairs($words):

   • 이 함수는 i
   • isPrefixAndSuffix()를 호출하여 단어[i]가 단어[j]의 접두사이자 접미사인지 확인합니다.
   • 조건이 true일 경우 카운트를 증가시킵니다.

2. isPrefixAndSuffix($str1, $str2):

   • 이 도우미 함수는 str1이 str2의 접두사이자 접미사인지 확인합니다.
   • substr()을 사용하여 str2의 접두사와 접미사를 추출하고 이를 str1과 비교합니다.
   • 두 조건이 모두 true이면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

시간 복잡도:

• 시간 복잡도는 O(n² x m)입니다. 여기서 n은 단어 배열의 길이이고 m은 단어 배열의 평균 길이입니다. 배열의 문자열. 이는 중첩 루프와 substr() 작업 때문입니다.

예제 출력:

주어진 입력 배열의 경우:

• ["a", "aba", "ababa", "aa"] -> 출력: 4
• ["아빠", "아빠", "엄마", "엄마"] -> 출력: 2
• ["abab", "ab"] -> 출력: 0

이 솔루션은 주어진 제약 내에서 효율적으로 작동해야 합니다.

연락처 링크

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

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

• 링크드인
• 깃허브

---

1. 접두사 문자열의 접두사는 문자열의 시작 부분에서 시작하여 문자열 내의 모든 지점까지 확장되는 하위 문자열입니다. ↩

2. 접미사 문자열의 접미사는 문자열의 임의 지점에서 시작하여 끝까지 이어지는 하위 문자열입니다. ↩

위 내용은 접두사 및 접미사 쌍 계산 I의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!