범위에서 모음 문자열 계산

2559. 범위에서 모음 문자열 계산

난이도:중

주제: 배열, 문자열, 접두사 합계

인덱스가 0인 문자열 단어 배열과 정수 쿼리의 2D 배열이 제공됩니다.

각 쿼리 쿼리[i] = [l_i, r_i]는 l_i 범위에 있는 문자열 수를 찾도록 요청합니다. r_i(둘 다 포함) 모음으로 시작하고 끝나는 단어입니다.

querys.length 크기의 배열 ans를 반환합니다. 여기서 ans[i]는 i^번째 쿼리에 대한 답변입니다.

참고 모음 글자는 'a', 'e', ​​'i', 'o', 'u'입니다.

예 1:

• 입력: 단어 = ["aba","bcb","ece","aa","e"], 쿼리 = [[0,2],[1,4],[1, 1]]
• 출력: [2,3,0]
• 설명: 모음으로 시작하고 끝나는 문자열은 "aba", "ece", "aa" 및 "e"입니다.
  • 쿼리 [0,2]에 대한 답은 2(문자열 "aba" 및 "ece")입니다.
  • 쿼리 [1,4]는 3(문자열 "ece", "aa", "e")입니다.
  • [1,1]을 쿼리하는 것은 0입니다.
  • [2,3,0]을 반환합니다.

예 2:

• 입력: 단어 = ["a","e","i"], 쿼리 = [[0,2],[0,1],[2,2]]
• 출력: [3,2,1]
• 설명: 모든 문자열이 조건을 만족하므로 [3,2,1]을 반환합니다.

제약조건:

• 1 5
• 1 <= 단어[i].length <= 40
• word[i]는 영문 소문자로만 구성됩니다.
• sum(단어[i].length) <= 3 * 10⁵
• 1 <= query.length <= 10⁵
• 0 <= l_i <= r_i < 단어.길이

힌트:

1. 모음으로 시작하고 끝나는 문자열의 접두어 합을 미리 계산합니다.
2. 모음을 저장하려면 unordered_set을 사용하세요.
3. 모음 집합에 문자열의 첫 글자와 마지막 글자가 있는지 확인하세요.
4. 모음으로 시작하고 끝나는 문자열의 수를 찾으려면 [l-1, r] 범위의 접두어 합을 뺍니다.

해결책:

다음 단계를 따르세요.

1. 모음 문자열 확인: 문자열이 모음으로 시작하고 끝나는지 확인하는 도우미 함수를 만듭니다.
2. 접두사 합계 미리 계산: 모음으로 시작하고 끝나는 문자열의 누적 개수를 저장하려면 접두사 합계 배열을 사용하세요.
3. 답변 쿼리: 접두사 합계 배열을 사용하면 각 쿼리에 대해 지정된 범위 내의 해당 문자열 수를 효율적으로 계산할 수 있습니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 2559. 범위 내에서 모음 문자열 계산

  
  
  설명:




isVowelString 함수:


문자열의 첫 글자와 마지막 글자가 모음인지 확인합니다.
in_array를 사용하여 문자가 사전 정의된 모음 목록에 있는지 확인합니다.



접두사 합계 배열:



prefixSum[i]는 인덱스 i-1까지 모음 문자열의 누적 개수를 저장합니다.
현재 단어가 조건을 만족하면 개수를 증가시킵니다.



쿼리 해결:


범위 [l, r]의 경우 모음 문자열의 개수는 prefixSum[r 1] - prefixSum[l]입니다.



효율성:


접두사 합계 배열을 구성하려면 O(n)이 필요합니다. 여기서 n은 단어 수입니다.
각 쿼리를 해결하려면 O(1)이 필요하므로 전체적인 복잡성은 O(n q)이 됩니다. 여기서 q는 쿼리 개수입니다.





  
  
  엣지 케이스:



모든 문자열은 모음으로 시작하고 끝납니다.
모음으로 시작하고 끝나는 문자열은 없습니다.
쿼리의 단일 요소 범위.


이 접근 방식은 문제의 제약 조건을 효율적으로 처리합니다.

연락처 링크

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

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


링크드인
깃허브



          

            
        
위 내용은 범위에서 모음 문자열 계산의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!