What is the most efficient way to find a string in a group of string?

general
, ,
1

Ex:
string=“King”
arr=[“Queen”, “Pawn”, “Kaleen”, “Munna”, “King”, “Minister”]
we need to find if “king” is present in arr or not…

2

This is a very simple question. Following code will work.

#include<bits/stdc++.h>
using namespace std ;
int main(){
  string find="King" ;
  bool check1=0;
  string arr[]={"Queen", "Pawn", "Kaleen", "Munna", "King", "Minister"} ;
  for(int i=0;i<6;i++){
    int N = find.size() ;
    int M = arr[i].size() ;
     bool check =1 ;
    for(int j=0;j<min(N,M);j++){
      if(find[j]!=arr[i][j]){
        check=0 ;
      }
    }
    if(check)
      cout << "YES" ,check1=1;
  }
  if(!check1)
    cout <<"NO" ;
  
}
3

It’s better to store strings in a hashtable and finding the string in it. Average time complexity is O(1).

1 Like
4

Which language do u use:

In python this works:

if requiredString in Strings:
      print ('yes')
else:
       print('no')

In cpp you can do something like this:

void solve()
{

unordered_map < string , int > mp ;

int n ;

cin >> n ; 

string a ;

for(int i = 0 ; i < n ; ++i) {
    cin >> a ;
    mp[a]++ ;
}

string req ;

cin >> req ;

cout << ((mp[req] >= 1) ? "yes" : "no") ;

}
5

You might want to use Trie Data Structure. Sets will also Work.
Using Trie: O(|S|)
Using Sets: O(|S|. log(|arr|)).

Example in Python:

arr = set(arr)
print(input() in arr)