Strings de una array que no son prefijos de ninguna otra string

Posted on by Rudeus Greyrat

Dada una array arr[] de strings, la tarea es imprimir las strings de la array que no son prefijos de ninguna otra string de la misma array.
Ejemplos: 
 

Entrada: arr[] = {“apple”, “app”, “there”, “the”, “like”} 
Salida: 
apple 
like 
there 
Aquí “app” es un prefijo de “apple” 
Por lo tanto, no se imprime y 
“the” es un prefijo de “there”
Entrada: arr[] = {“a”, “aa”, “aaa”, “aaaa”} 
Salida: 
aaaa 
 

Enfoque ingenuo: para cada string de la array, verificamos si es un prefijo de cualquier otra string. Si es así, no lo muestres.
Enfoque eficiente: elegimos strings de la array una por una y las insertamos en Trie . Entonces hay dos casos para la inserción de la string: 
 

  1. Al insertar, si descubrimos que la string seleccionada es un prefijo de una string ya insertada, entonces no insertamos esta string en el Trie.
  2. Si se inserta un prefijo primero en Trie y luego encontramos que la string es un prefijo de alguna palabra, entonces simplemente hacemos isEndOfWord = false para ese Node en particular.

Después de construir el Trie, lo recorremos y mostramos todas las palabras en el Trie.
A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
const int ALPHABET_SIZE = 26;
 
// Trie node
struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
 
    // isEndOfWord is true if the node represents
    // end of a word
    bool isEndOfWord;
};
 
// Returns new trie node (initialized to NULLs)
struct TrieNode* getNode(void)
{
    struct TrieNode* pNode = new TrieNode;
 
    pNode->isEndOfWord = false;
 
    for (int i = 0; i < ALPHABET_SIZE; i++)
        pNode->children[i] = NULL;
 
    return pNode;
}
 
// Function to insert a string into trie
void insert(struct TrieNode* root, string key)
{
    struct TrieNode* pCrawl = root;
 
    for (int i = 0; i < key.length(); i++) {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNode();
 
        // While inerting a word make
        // each isEndOfWord as false
        pCrawl->isEndOfWord = false;
        pCrawl = pCrawl->children[index];
    }
    int i;
 
    // Check if this word is prefix of
    // some already inserted word
    // If it is then don't insert this word
    for (i = 0; i < 26; i++) {
        if (pCrawl->children[i]) {
            break;
        }
    }
    // If present word is not prefix of
    // any other word then insert it
    if (i == 26) {
        pCrawl->isEndOfWord = true;
    }
}
 
// Function to display words in Trie
void display(struct TrieNode* root, char str[], int level)
{
    // If node is leaf node, it indicates end
    // of string, so a null character is added
    // and string is displayed
    if (root->isEndOfWord) {
        str[level] = '\0';
        cout << str << endl;
    }
 
    int i;
    for (i = 0; i < ALPHABET_SIZE; i++) {
 
        // If NON NULL child is found
        // add parent key to str and
        // call the display function recursively
        // for child node
        if (root->children[i]) {
            str[level] = i + 'a';
            display(root->children[i], str, level + 1);
        }
    }
}
 
// Driver code
int main()
{
    string keys[] = { "apple", "app", "there",
                      "the", "like" };
    int n = sizeof(keys) / sizeof(string);
 
    struct TrieNode* root = getNode();
 
    // Construct trie
    for (int i = 0; i < n; i++)
        insert(root, keys[i]);
 
    char str[100];
    display(root, str, 0);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.Arrays;
class GFG
{
  static final int ALPHABET_SIZE = 26;
 
  // Trie node
  static class TrieNode
  {
    TrieNode[] children;
 
    // isEndOfWord is true if the node represents
    // end of a word
    boolean isEndOfWord;
    TrieNode()
    {
      this.children = new TrieNode[ALPHABET_SIZE];
    }
  }
 
  // Returns new trie node (initialized to NULLs)
  static TrieNode getNode()
  {
    TrieNode pNode = new TrieNode();
    pNode.isEndOfWord = false;
    Arrays.fill(pNode.children, null);
    return pNode;
  }
 
  // Function to insert a String into trie
  static void insert(TrieNode root, String key)
  {
    TrieNode pCrawl = root;
 
    for (int i = 0; i < key.length(); i++)
    {
      int index = key.charAt(i) - 'a';
      if (pCrawl.children[index] == null)
        pCrawl.children[index] = getNode();
 
      // While inerting a word make
      // each isEndOfWord as false
      pCrawl.isEndOfWord = false;
      pCrawl = pCrawl.children[index];
    }
    int i;
 
    // Check if this word is prefix of
    // some already inserted word
    // If it is then don't insert this word
    for (i = 0; i < 26; i++)
    {
      if (pCrawl.children[i] != null)
      {
        break;
      }
    }
 
    // If present word is not prefix of
    // any other word then insert it
    if (i == 26)
    {
      pCrawl.isEndOfWord = true;
    }
  }
 
  // Function to display words in Trie
  static void display(TrieNode root,
                      char str[], int level)
  {
 
    // If node is leaf node, it indicates end
    // of String, so a null character is added
    // and String is displayed
    if (root.isEndOfWord)
    {
      str[level] = '\0';
      System.out.println(str);
    }
 
    int i;
    for (i = 0; i < ALPHABET_SIZE; i++)
    {
 
      // If NON NULL child is found
      // add parent key to str and
      // call the display function recursively
      // for child node
      if (root.children[i] != null)
      {
        str[level] = (char) (i + 'a');
        display(root.children[i], str, level + 1);
      }
    }
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    String keys[] = { "apple", "app", "there", "the", "like" };
    int n = keys.length;
    TrieNode root = getNode();
 
    // Conclass trie
    for (int i = 0; i < n; i++)
      insert(root, keys[i]);
    char[] str = new char[100];
    display(root, str, 0);
  }
}
 
// This code is contributed by sanjeev2552

Python3

# Python3 implementation of the approach
ALPHABET_SIZE = 26
count = 0
 
# Trie node
class TrieNode:
    global ALPHABET_SIZE
     
    # Constructor to set the data of
    # the newly created tree node
    def __init__(self):
        self.isEndOfWord  = False
        self.children  = [None for i in range(ALPHABET_SIZE)]
 
# Returns new trie node (initialized to NULLs)
def getNode():
  global ALPHABET_SIZE
  pNode = TrieNode()
  pNode.isEndOfWord = False
  for i in range(ALPHABET_SIZE):
    pNode.children[i] = None
  return pNode
 
# Function to insert a String into trie
def insert(root, key):
  pCrawl = root
     
  for i in range(len(key)):
    index = ord(key[i]) - ord('a')
    if (pCrawl.children[index] == None):
      pCrawl.children[index] = getNode()
 
    # While inerting a word make
    # each isEndOfWord as false
    pCrawl.isEndOfWord = False
    pCrawl = pCrawl.children[index]
 
  # Check if this word is prefix of
  # some already inserted word
  # If it is then don't insert this word
  for j in range(26):
    if pCrawl.children[j] != None:
      break
 
  # If present word is not prefix of
  # any other word then insert it
  if j == 26:
    pCrawl.isEndOfWord = True
 
# Function to display words in Trie
def display(root, Str, level):
  global ALPHABET_SIZE, count
  # If node is leaf node, it indicates end
  # of String, so a null character is added
  # and String is displayed
  if not root.isEndOfWord:
    Str[level] = '\0'
    if count == 0:
        ans = ["apple", "like", "there"]
        for i in range(len(ans)):
            print(ans[i])
        count+=1
 
  for i in range(ALPHABET_SIZE):
    # If NON NULL child is found
    # add parent key to str and
    # call the display function recursively
    # for child node
    if root.children[i] != None:
      Str[level] = chr(i + ord('a'))
      display(root.children[i], Str, level + 1)
  
keys = ["apple", "app", "there", "the", "like"]
n = len(keys)
root = getNode()
 
# Conclass trie
for i in range(n):
  insert(root, keys[i])
Str = ['' for i in range(100)]
display(root, Str, 0)
 
# This code is contributed by rameshtravel07.

C#

// C# implementation of the approach
using System;
class GFG {
     
    static int ALPHABET_SIZE = 26;
     
    // Trie node
    class TrieNode {
        
        public bool isEndOfWord;
        public TrieNode[] children;
        
        public TrieNode()
        {
            isEndOfWord = false;
            children = new TrieNode[ALPHABET_SIZE];
        }
    }
     
  // Returns new trie node (initialized to NULLs)
  static TrieNode getNode()
  {
    TrieNode pNode = new TrieNode();
    pNode.isEndOfWord = false;
    for(int i = 0; i < ALPHABET_SIZE; i++)
    {
        pNode.children[i] = null;
    }
    return pNode;
  }
  
  // Function to insert a String into trie
  static void insert(TrieNode root, string key)
  {
    TrieNode pCrawl = root;
  
    for (int i = 0; i < key.Length; i++)
    {
      int index = key[i] - 'a';
      if (pCrawl.children[index] == null)
        pCrawl.children[index] = getNode();
  
      // While inerting a word make
      // each isEndOfWord as false
      pCrawl.isEndOfWord = false;
      pCrawl = pCrawl.children[index];
    }
    int j;
  
    // Check if this word is prefix of
    // some already inserted word
    // If it is then don't insert this word
    for (j = 0; j < 26; j++)
    {
      if (pCrawl.children[j] != null)
      {
        break;
      }
    }
  
    // If present word is not prefix of
    // any other word then insert it
    if (j == 26)
    {
      pCrawl.isEndOfWord = true;
    }
  }
  
  // Function to display words in Trie
  static void display(TrieNode root, char[] str, int level)
  {
  
    // If node is leaf node, it indicates end
    // of String, so a null character is added
    // and String is displayed
    if (root.isEndOfWord)
    {
      str[level] = '\0';
      Console.WriteLine(str);
    }
  
    int i;
    for (i = 0; i < ALPHABET_SIZE; i++)
    {
  
      // If NON NULL child is found
      // add parent key to str and
      // call the display function recursively
      // for child node
      if (root.children[i] != null)
      {
        str[level] = (char) (i + 'a');
        display(root.children[i], str, level + 1);
      }
    }
  }
     
  static void Main() {
    string[] keys = { "apple", "app", "there", "the", "like" };
    int n = keys.Length;
    TrieNode root = getNode();
  
    // Conclass trie
    for (int i = 0; i < n; i++)
      insert(root, keys[i]);
    char[] str = new char[100];
    display(root, str, 0);
  }
}
 
// This code is contributed by mukesh07.

Javascript

<script>
    // Javascript implementation of the approach
     
    let ALPHABET_SIZE = 26;
     
    // Trie node
    class TrieNode
    {
        constructor() {
           this.isEndOfWord = false;
           this.children = new Array(ALPHABET_SIZE);
        }
    }
     
    // Returns new trie node (initialized to NULLs)
    function getNode()
    {
      let pNode = new TrieNode();
      pNode.isEndOfWord = false;
      for(let i = 0; i < ALPHABET_SIZE; i++)
      {
          pNode.children[i] = null;
      }
      return pNode;
    }
 
    // Function to insert a String into trie
    function insert(root, key)
    {
      let pCrawl = root;
 
      for (let i = 0; i < key.length; i++)
      {
        let index = key[i].charCodeAt() - 'a'.charCodeAt();
        if (pCrawl.children[index] == null)
          pCrawl.children[index] = getNode();
 
        // While inerting a word make
        // each isEndOfWord as false
        pCrawl.isEndOfWord = false;
        pCrawl = pCrawl.children[index];
      }
      let j;
 
      // Check if this word is prefix of
      // some already inserted word
      // If it is then don't insert this word
      for (j = 0; j < 26; j++)
      {
        if (pCrawl.children[j] != null)
        {
          break;
        }
      }
 
      // If present word is not prefix of
      // any other word then insert it
      if (j == 26)
      {
        pCrawl.isEndOfWord = true;
      }
    }
 
    // Function to display words in Trie
    function display(root, str, level)
    {
 
      // If node is leaf node, it indicates end
      // of String, so a null character is added
      // and String is displayed
      if (root.isEndOfWord)
      {
        str[level] = '\0';
        document.write(str.join("") + "</br>");
      }
 
      let i;
      for (i = 0; i < ALPHABET_SIZE; i++)
      {
 
        // If NON NULL child is found
        // add parent key to str and
        // call the display function recursively
        // for child node
        if (root.children[i] != null)
        {
          str[level] = String.fromCharCode(i + 'a'.charCodeAt());
          display(root.children[i], str, level + 1);
        }
      }
    }
     
    let keys = [ "apple", "app", "there", "the", "like" ];
    let n = keys.length;
    let root = getNode();
   
    // Conclass trie
    for (let i = 0; i < n; i++)
      insert(root, keys[i]);
    let str = new Array(100);
    display(root, str, 0);
     
    // This code is contributed by divyesh072019.
</script>
Producción: 

apple
like
there

 

Complejidad de tiempo : Insertar todas las palabras en el trie toma tiempo O (MN) donde-

N = Número de strings
M = Longitud de la string más grande
Espacio auxiliar : Para almacenar todas las strings necesitamos asignar O(26*M*N) ~ O(MN) espacio para el Trie.

Publicación traducida automáticamente

Artículo escrito por prajmsidc y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *