Cuente las ocurrencias de strings formadas usando palabras en otra string

Dada una string A y un vector de strings B , la tarea es contar el número de strings en el vector B que solo contiene las palabras de A.

Ejemplos:

Entrada: A=”azul verde rojo amarillo”
B[]={“azul rojo”, “verde rosa”, “amarillo verde”}
Salida: 2

Entrada: A=”manzana plátano pera”
B[]={“manzana”, “manzana plátano”, “pera plátano”}
Salida: 3

Enfoque: siga los pasos a continuación para resolver este problema:

1. Extrae todas las palabras de la string A y guárdalas en un conjunto, digamos st .
2. Ahora recorra cada string en el vector B y obtenga todas las palabras en esa string.
3. Ahora verifique que si todas las palabras están presentes en st , entonces incremente ans en 1 .
4. Regresa ans como la solución al problema.

A continuación se muestra la implementación del enfoque anterior:

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to extract all words from a string
vector<string> getWords(string A)
{
    vector<string> words;
    string t;
    for (int i = 0; i < A.size(); i++) {
 
        // If the character is a space
        if (A[i] == ' ') {
            if (t.size() > 0) {
                words.push_back(t);
            }
            t = "";
        }
 
        // Else
        else {
            t += A[i];
        }
    }
 
    // Last word
    if (t.size() > 0) {
        words.push_back(t);
    }
 
    return words;
}
 
// Function to count the number of strings in B
// that only contains the words from A
int countStrings(string A, vector<string>& B)
{
 
    unordered_set<string> st;
 
    vector<string> words;
    words = getWords(A);
 
    for (auto x : words) {
        st.insert(x);
    }
 
    // Variable to store the final answer
    int ans = 0;
    for (auto x : B) {
        words = getWords(x);
        bool flag = 0;
        for (auto y : words) {
            if (st.find(y) == st.end()) {
                flag = 1;
                break;
            }
        }
 
        // If all the words are in set st
        if (!flag) {
            ans++;
        }
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    string A = "blue green red yellow";
    vector<string> B = { "blue red", "green pink", "yellow green" };
 
    cout << countStrings(A, B);
}

// Java code for the above approach
import java.util.*;
 
class GFG
{
 
  // Function to extract all words from a String
  static Vector<String> getWords(String A)
  {
    Vector<String> words = new Vector<String>();
    String t="";
    for (int i = 0; i < A.length(); i++) {
 
      // If the character is a space
      if (A.charAt(i) == ' ') {
        if (t.length() > 0) {
          words.add(t);
        }
        t = "";
      }
 
      // Else
      else {
        t += A.charAt(i);
      }
    }
 
    // Last word
    if (t.length() > 0) {
      words.add(t);
    }
 
    return words;
  }
 
  // Function to count the number of Strings in B
  // that only contains the words from A
  static int countStrings(String A, String[] B)
  {
 
    HashSet<String> st = new HashSet<>();
 
    Vector<String> words = new Vector<String>();
    words = getWords(A);
 
    for (String x : words) {
      st.add(x);
    }
 
    // Variable to store the final answer
    int ans = 0;
    for (String x : B) {
      words = getWords(x);
      boolean flag = false;
      for (String y : words) {
        if (!st.contains(y)) {
          flag = true;
          break;
        }
      }
 
      // If all the words are in set st
      if (!flag) {
        ans++;
      }
    }
 
    return ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    String A = "blue green red yellow";
    String []B = { "blue red", "green pink", "yellow green" };
 
    System.out.print(countStrings(A, B));
  }
}
 
// This code is contributed by 29AjayKumar

# Python 3  code for the above approach
 
# Function to extract all words from a string
def getWords(A):
    words = []
    t = ""
    for i in range(len(A)):
 
        # If the character is a space
        if (A[i] == ' '):
            if (len(t) > 0):
                words.append(t)
 
            t = ""
 
        # Else
        else:
            t += A[i]
 
    # Last word
    if (len(t) > 0):
        words.append(t)
 
    return words
 
# Function to count the number of strings in B
# that only contains the words from A
def countStrings(A, B):
    st = set([])
 
    words = []
    words = getWords(A)
 
    for x in words:
        st.add(x)
 
    # Variable to store the final answer
    ans = 0
    for x in B:
        words = getWords(x)
        flag = 0
        for y in words:
            if (y not in st):
                flag = 1
                break
 
        # If all the words are in set st
        if (not flag):
            ans += 1
 
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    A = "blue green red yellow"
    B = ["blue red", "green pink", "yellow green"]
 
    print(countStrings(A, B))
 
    # This code is contributed by ukasp.

// C# code for the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Function to extract all words from a String
  static List<String> getWords(String A)
  {
    List<String> words = new List<String>();
    String t="";
    for (int i = 0; i < A.Length; i++) {
 
      // If the character is a space
      if (A[i] == ' ') {
        if (t.Length > 0) {
          words.Add(t);
        }
        t = "";
      }
 
      // Else
      else {
        t += A[i];
      }
    }
 
    // Last word
    if (t.Length > 0) {
      words.Add(t);
    }
 
    return words;
  }
 
  // Function to count the number of Strings in B
  // that only contains the words from A
  static int countStrings(String A, String[] B)
  {
 
    HashSet<String> st = new HashSet<String>();
 
    List<String> words = new List<String>();
    words = getWords(A);
 
    foreach (String x in words) {
      st.Add(x);
    }
 
    // Variable to store the readonly answer
    int ans = 0;
    foreach (String x in B) {
      words = getWords(x);
      bool flag = false;
      foreach (String y in words) {
        if (!st.Contains(y)) {
          flag = true;
          break;
        }
      }
 
      // If all the words are in set st
      if (!flag) {
        ans++;
      }
    }
 
    return ans;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    String A = "blue green red yellow";
    String []B = { "blue red", "green pink", "yellow green" };
 
    Console.Write(countStrings(A, B));
  }
}
 
// This code is contributed by 29AjayKumar

  <script>
      // JavaScript code for the above approach
 
      // Function to extract all words from a string
      function getWords(A) {
          let words = [];
          let t;
          for (let i = 0; i < A.length; i++) {
 
              // If the character is a space
              if (A[i] == ' ') {
                  if (t.length > 0) {
                      words.push(t);
                  }
                  t = "";
              }
 
              // Else
              else {
                  t += A[i];
              }
          }
 
          // Last word
          if (t.length > 0) {
              words.push(t);
          }
 
          return words;
      }
 
      // Function to count the number of strings in B
      // that only contains the words from A
      function countStrings(A, B) {
 
          let st = new Set();
 
          let words;
          words = getWords(A);
 
          for (let x of words) {
              st.add(x);
          }
 
          // Variable to store the final answer
          let ans = 0;
          for (let x of B) {
              words = getWords(x);
              let flag = 0;
              for (let y = 0; y < words.length; y++) {
                  if (st.has(words[y])) {
                      flag = 1;
                      break;
                  }
              }
 
              // If all the words are in set st
              if (flag == 0) {
                  ans++;
              }
          }
 
          return ans + 1;
      }
 
      // Driver Code
      let A = "blue green red yellow";
      let B = ["blue red", "green pink", "yellow green"];
 
      document.write(countStrings(A, B));
 
 
// This code is contributed by Potta Lokesh
  </script>

2

Complejidad temporal: O(N*M), donde N es el tamaño del vector B y M es la longitud máxima de B.
Espacio auxiliar: O(N)