配列Leetcodeソリューションでの文字列照合


難易度 簡単に
よく聞かれる Amazon (アマゾン)
文字列

配列Leetcodeソリューションでの文字列照合の問題は、文字列の配列を提供します。 問題は、他のいくつかの部分文字列である文字列を見つけるように私たちに求めています 文字列 入力から。 簡単に言うと、部分文字列は、両端から文字を削除した後に残っている文字列の一部にすぎません。 両端から0文字を削除することもできます。 また、削除される文字の数は同じである必要はありません。 したがって、理解を深めるために、いくつかの例を見てみましょう。

配列Leetcodeソリューションでの文字列照合

words = ["mass","as","hero","superhero"]
["as","hero"]

説明:出力は「mass」であるため、「as」になります。 同様に、「ヒーロー」は「スーパーヒーロー」の一部です。 したがって、入力でもある入力の部分文字列を単純に見つけました。

words = ["leetcode","et","code"]
["et","code"]

説明:この例は、サブストリングが同じストリングからのものである可能性があることを示しています。 ここのように、出力の両方の文字列は「leetcode」のサブ文字列です。

配列Leetcodeソリューションでの文字列照合のアプローチ

この問題により、特定の条件を満たす入力から文字列を選択するように求められました。 条件は、文字列が入力にも含まれる文字列のサブ文字列である必要があることです。 したがって、他の文字列のサブ文字列である文字列を見つけるこのプロセスをシミュレートしようとします。 残っている唯一の問題は実装です。 したがって、ハッシュセットまたは順序付けされていないマップを使用して、出力として機能する文字列を追跡します。 i番目のインデックスの文字列がj番目のインデックスの文字列のサブ文字列であるかどうかをチェックするXNUMXつのネストされたループを使用し、その逆も同様です。 C ++では、XNUMX番目の文字列が最初の引数の部分文字列であるかどうかをチェックする独自の関数を作成しました。 Javaでは、これはcontains()関数を使用して簡単に見つけることができます。

配列Leetcodeソリューションでの文字列照合のコード

C ++コード

#include <bits/stdc++.h>
using namespace std;

bool isSubstr(string a, string b){
    int n = a.size(), m = b.size();
    for(int i=0;i<=n-m;i++){
        if(a.substr(i, m) == b)
            return true;
    }
    return false;
}

vector<string> stringMatching(vector<string>& words) {
    unordered_set<string> tmp;
    int n = words.size();
    for(int i=0;i<n-1;i++){
        string curWord = words[i];
        for(int j=i+1;j<n;j++){
            string nextWord = words[j];
            if(isSubstr(curWord, nextWord))
                tmp.insert(nextWord);
            if(isSubstr(nextWord, curWord))
                tmp.insert(curWord);
        }
    }
    return vector<string>(tmp.begin(), tmp.end());
}

int main(){
    vector<string> input({"mass","as","hero","superhero"});
    vector<string> v = stringMatching(input);
    for(auto x: v)
        cout<<x<<" ";
}
hero as

Javaコード

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<String> stringMatching(String[] words) {
        HashSet<String> tmp = new HashSet<>();
        
        int n = words.length;
        for(int i = 0; i<n-1; i++) {
            String curWord = words[i];
            for(int j = i+1; j<n; j++) {
                String nextWord = words[j];
                if(curWord.contains(nextWord))
                    tmp.add(nextWord);
                if(nextWord.contains(curWord))
                    tmp.add(curWord);
            }
        }
        
        return new ArrayList<String>(tmp);
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    String[] words = {"mass","as","hero","superhero"};
    List<String> list = stringMatching(words);
    for(String x: list)
      System.out.print(x+" ");
  }
}
hero as

複雑さの分析

時間の複雑さ

O(N ^ 2 * | S |)、 入力文字列の数に依存するXNUMXつのネストされたループを使用したためです。 次に、文字列が他のニーズの部分文字列であるかどうかを見つけるために使用される関数 O(| S |) 時間。

スペースの複雑さ

オン)、 最悪の場合、入力全体が出力になる可能性があります。 したがって、空間の複雑さは線形です。