접두사 및 접미사 쌍 계산 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 <인 인덱스 쌍(i, j)의

번호

를 나타내는 정수를 반환합니다. 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 <= 단어.길이 <= 50

• 1 <= 단어[i].length <= 10
• word[i]는 영문 소문자로만 구성됩니다.

힌트:

모든 인덱스 쌍(i, j)을 반복하여 i < j, isPrefixAndSuffix(words[i],words[j])를 확인하세요.

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

해결책:

i <인 경우 모든 인덱스 쌍(i, j)을 반복해야 합니다. j 그리고 문자열 word[i]가 word[j]의 접두사이자 접미사인지 확인합니다. 각 쌍에 대해 PHP 내장 함수 substr()을 사용하여 접두사와 접미사를 확인할 수 있습니다.

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

  
  
  설명:




countPrefixAndSuffixPairs($words):


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



isPrefixAndSuffix($str1, $str2):


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





  
  
  시간 복잡도:



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



  
  
  예제 출력:


주어진 입력 배열의 경우:



["a", "aba", "ababa", "aa"] -> 출력: 4


["아빠", "아빠", "엄마", "엄마"] -> 출력: 2


["abab", "ab"] -> 출력: 0



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

연락처 링크

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

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


링크드인
깃허브








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



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





          

            
  

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