fork download
copy 
  1. #include<bits//stdc++.h>
  2. using namespace std;
  3. #define INF 1e8
  4. /*
  5.     Time Complexity: O(M^2*(N))
  6.     Space Complexity: O(1)
  7.  
  8.      Where N and M are the total lengths of all tickets and the length of the match string.
  9. */
  10.  
  11. // Helper Function to match the characters according to the given conditions
  12. bool matchChar(char char1, char char2)
  13. {
  14.     if(char1 == char2)
  15.     {
  16.         return true;
  17.     }
  18.  
  19.     if((char1 == 'a' && char2 == 'o') || (char1 == 'o' && char2 == 'a'))
  20.     {
  21.         return true;
  22.     }
  23.  
  24.     if((char1 == 't' && char2 == 'l') || (char1 == 'l' && char2 == 't'))
  25.     {
  26.         return true;
  27.     }
  28.  
  29.     return false;
  30. }
  31.  
  32.  
  33. // Check if the subtring matches with the ticket with at most K characters skipped
  34. bool match(string &matchStr, string &ticket, int k)
  35. {
  36.     // If the ticket is less then the string return False
  37.     if(matchStr.size() < ticket.size())
  38.         return false;
  39.  
  40.     int i = 0;
  41.     int j = 0;
  42.  
  43.     while(i < matchStr.size() && j < ticket.size())
  44.     {
  45.         if(matchChar(matchStr[i], ticket[j]))
  46.             j += 1;
  47.  
  48.         i += 1;
  49.     }
  50.  
  51.     // If all the characters of the ticket are not found return False
  52.     if(j != ticket.size())
  53.         return false;
  54.  
  55.     // If the substring length is greater by more than K characters return False
  56.     return i - j <= k ? true : false;
  57. }
  58.  
  59.  
  60. int lotteryTickets(string &matchStr, vector<string> &tickets, int k)
  61. {
  62.     int count = 0;
  63.  
  64.     // Iterate for each ticket
  65.     for(int z = 0; z < tickets.size(); z++)
  66.     {   
  67.         string ticket = tickets[z];
  68.  
  69.         bool found = false;
  70.  
  71.         // Iterate over every substring of the string
  72.         for(int i = 0; i < matchStr.size(); i++)
  73.         {  
  74.             string curr;
  75.  
  76.             for(int j = i; j < matchStr.size(); j++)
  77.             {
  78.                 curr += matchStr[j];
  79.  
  80.                 if(match(curr, ticket, k))
  81.                 {
  82.                     found = true;
  83.                     count += 1;
  84.                     break;
  85.                 }
  86.             }
  87.  
  88.             if(found)
  89.             {
  90.                 break;
  91.             }
  92.         }
  93.     }
  94.  
  95.     // Return the number of matched tickets
  96.     return count;
  97. }
  98. int main()
  99. {    
  100.    int n;
  101.    cin>>n;
  102.    string draw_string;
  103.    cin>>draw_string;
  104.    vector<string> ticket(n);
  105.    for(int i=0;i<n;i++)
  106.    {
  107.       cin>>ticket[i];
  108.    }
  109.    int k;
  110.    cin>>k;
  111.    int ans=lotteryTickets(draw_string,ticket,k);
  112.    cout<<ans<<endl;
  113.     return 0;
  114. }
Success #stdin #stdout 0.01s 5548KB
comments (?)
stdin
copy 
5
abcdl 
aob 
acld 
aobocd
aado
aabacdt 
1
stdout
copy 
0
https://ideone.com/urvJxs
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!