配列内の文字列のマッチング

1408。配列内の文字列のマッチング

難易度: 簡単

トピック: 配列、文字列、文字列マッチング

文字列単語の配列を指定すると、別の単語の部分文字列である単語内のすべての文字列を返します。回答は任意の順序で返すことができます。

部分文字列は、文字列

内の連続した文字のシーケンスです。

例 1:

• 入力: 単語 = ["マス","as","ヒーロー","スーパーヒーロー"]
• 出力: ["as","hero"]
• 説明: 「as」は「mass」の部分文字列で、「hero」は「superhero」の部分文字列です。 ["hero","as"] も有効な答えです。

例 2:

• 入力: 単語 = ["leetcode","et","code"]
• 出力: ["et","code"]
• 説明: 「et」、「code」は「leetcode」の部分文字列です。

例 3:

• 入力: 単語 = ["blue","green","bu"]
• 出力: []
• 説明: 単語の文字列は、別の文字列の部分文字列ではありません。

制約:

• 1
• 1
• Words[i] には小文字の英字のみが含まれます。
• 単語の文字列はすべて 一意です。

ヒント:

1. ある文字列が別の文字列の部分文字列であるかどうかをブルートフォースで検索するか、KMP アルゴリズムを使用します。

解決策:

単語配列内で、配列内の別の単語の部分文字列であるすべての文字列を検索する必要があります。総当たりアプローチを使用できます。このアプローチには、リスト内の各文字列をチェックし、それが他の文字列の部分文字列であるかどうかを確認することが含まれます。

このソリューションを PHP で実装してみましょう: 1408。配列内の文字列一致

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

// Example 1
$words = ["mass", "as", "hero", "superhero"];
print_r(stringMatching($words));

// Example 2
$words = ["leetcode", "et", "code"];
print_r(stringMatching($words));

// Example 3
$words = ["blue", "green", "bu"];
print_r(stringMatching($words));
?>

説明：

1. 関数 stringMatching は、入力配列内のすべての単語をループします。
2. 各単語について、入れ子になったループを使用して、配列内の他のすべての単語と比較します。
3. PHP の strpos() 関数を使用して、ある文字列が別の文字列の部分文字列であるかどうかを確認します。部分文字列が見つからない場合、strpos() 関数は false を返します。
4. 部分文字列が見つかった場合は、単語を 1 回記録するだけで済むため、その単語を結果の配列に追加し、内部ループから抜け出します。
5. 最後に、関数はすべての部分文字列を含む結果配列を返します。

時間計算量:

• 時間計算量は O(n² x m) です。ここで、n は次の数です。単語と m は最大長です一言。これは、1 つおきの単語内の各単語に対して部分文字列検索を実行しているためです。

出力例:

入力 ["mass"、"as"、"hero"、"superhero"] の場合、出力は次のようになります:

Array
(
    [0] => as
    [1] => hero
)

入力 ["leetcode", "et", "code"] の場合、出力は次のようになります:

Array
(
    [0] => et
    [1] => code
)

入力 ["blue"、"green"、"bu"] の場合、出力は次のようになります:

Array
(
)

この解決策は、特定の問題の制約に対してうまく機能します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

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

• LinkedIn
• GitHub

以上が配列内の文字列のマッチングの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。