範囲内の母音文字列を数える

2559。範囲内の母音文字列を数える

難易度: 中

トピック: 配列、文字列、プレフィックス合計

文字列ワードの 0 インデックス 配列と整数クエリの 2D 配列が与えられます。

各クエリ queries[i] = [l_i, r_i] は、l_i から までの範囲内に存在する文字列の数を見つけるように求めます。 r_i (両方を含む) 母音で始まり母音で終わる単語。

サイズ queries.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

Words[i] は英小文字のみで構成されています。

sum(words[i].length) 5

1 5

0 <= l

i

<= r_i <単語.長さ

ヒント:

母音で始まり母音で終わる文字列の接頭辞の合計を事前計算します。

1. 母音を保存するには unowned_set を使用します。
2. 文字列の最初と最後の文字が母音セットに存在するかどうかを確認します。
3. 範囲 [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 で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:


LinkedIn
GitHub



          

            
        
以上が範囲内の母音文字列を数えるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。