Compruebe si la string sigue el orden de los caracteres definidos por un patrón o no | conjunto 2

Dada una string de entrada y un patrón, verifique si los caracteres en la string de entrada siguen el mismo orden determinado por los caracteres presentes en el patrón. Suponga que no habrá caracteres duplicados en el patrón.
Otra solución al mismo problema se publica aquí .
Ejemplos: 
 

Input: string = "engineers rock", pattern = "er";
Output: true
All 'e' in the input string are before all 'r'.

Input: string = "engineers rock", pattern = "egr";
Output: false
There are two 'e' after 'g' in the input string.

Input: string = "engineers rock", pattern = "gsr";
Output: false
There are one 'r' before 's' in the input string.

La idea aquí es reducir la string dada al patrón dado. Para los caracteres dados en el patrón, solo mantenemos los caracteres correspondientes en la string. En la nueva string, eliminamos caracteres repetidos continuos. La string modificada debería ser igual al patrón dado. Por último, comparamos la string modificada con el patrón dado y devolvemos verdadero o falso en consecuencia.
Ilustración: 
 

str = "bfbaeadeacc", pat[] = "bac"

1) Remove extra characters from str (characters
  that are not present in pat[]
str = "bbaaacc"   [f, e and d are removed]

3) Removed consecutive repeating occurrences of 
   characters
str = "bac"   

4) Since str is same as pat[], we return true

A continuación se muestra la implementación de los pasos anteriores.
 

// Java program to check if characters of a string follow
// pattern defined by given pattern.
import java.util.*;
 
public class OrderOfCharactersForPattern
{
    public static boolean followsPattern(String str, String pattern)
    {
        // Insert all characters of pattern in a hash set,
        Set<Character> patternSet = neHashSet<>();
        for (int i=0; i<pattern.length(); i++)
            patternSet.add(pattern.charAt(i));
 
        // Build modified string (string with characters only from
        // pattern are taken)
        StringBuilder modifiedString = new StringBuilder(str);
        for (int i=str.length()-1; i>=0; i--)
            if (!patternSet.contains(modifiedString.charAt(i)))
                modifiedString.deleteCharAt(i);
 
        // Remove more than one consecutive occurrences of pattern
        // characters from modified string.
        for (int i=modifiedString.length()-1; i>0; i--)
            if (modifiedString.charAt(i) == modifiedString.charAt(i-1))
                modifiedString.deleteCharAt(i);
 
        // After above modifications, the length of modified string
        // must be same as pattern length
        if (pattern.length() != modifiedString.length())
            return false;
 
        // And pattern characters must also be same as modified string
        // characters
        for (int i=0; i<pattern.length(); i++)
            if (pattern.charAt(i) != modifiedString.charAt(i))
                return false;
 
        return true;
    }
 
    // Driver program
    int main()
    {
        String str = "engineers rock";
        String pattern = "er";
        System.out.println("Expected: true, Actual: " +
                           followsPattern(str, pattern));
 
        str = "engineers rock";
        pattern = "egr";
        System.out.println("Expected: false, Actual: " +
                          followsPattern(str, pattern));
 
        str = "engineers rock";
        pattern = "gsr";
        System.out.println("Expected: false, Actual: " +
                           followsPattern(str, pattern));
 
        str = "engineers rock";
        pattern = "eger";
        System.out.println("Expected: true, Actual: " +
                           followsPattern(str, pattern));
 
        return 0;
    }
}

# Python3 program to check if characters of
# a string follow pattern defined by given pattern.
def followsPattern(string, pattern):
 
    # Insert all characters of pattern in a hash set,
    patternSet = set()
 
    for i in range(len(pattern)):
        patternSet.add(pattern[i])
 
    # Build modified string (string with characters
    # only from pattern are taken)
    modifiedString = string
    for i in range(len(string) - 1, -1, -1):
        if not modifiedString[i] in patternSet:
            modifiedString = modifiedString[:i] + \
                             modifiedString[i + 1:]
 
    # Remove more than one consecutive occurrences
    # of pattern characters from modified string.
    for i in range(len(modifiedString) - 1, 0, -1):
        if modifiedString[i] == modifiedString[i - 1]:
            modifiedString = modifiedString[:i] + \
                             modifiedString[i + 1:]
 
    # After above modifications, the length of
    # modified string must be same as pattern length
    if len(pattern) != len(modifiedString):
        return False
 
    # And pattern characters must also be same
    # as modified string characters
    for i in range(len(pattern)):
        if pattern[i] != modifiedString[i]:
            return False
    return True
 
# Driver Code
if __name__ == "__main__":
    string = "engineers rock"
    pattern = "er"
    print("Expected: true, Actual:",
           followsPattern(string, pattern))
 
    string = "engineers rock"
    pattern = "egr"
    print("Expected: false, Actual:",
           followsPattern(string, pattern))
 
    string = "engineers rock"
    pattern = "gsr"
    print("Expected: false, Actual:",
           followsPattern(string, pattern))
 
    string = "engineers rock"
    pattern = "eger"
    print("Expected: true, Actual:",
           followsPattern(string, pattern))
 
# This code is contributed by
# sanjeev2552

// C# program to check if characters of a string follow
// pattern defined by given pattern.
using System;
using System.Collections.Generic;
using System.Text;
 
class GFG
{
    public static bool followsPattern(String str, String pattern)
    {
        // Insert all characters of pattern in a hash set,
        HashSet<char> patternSet = new HashSet<char>();
        for (int i = 0; i < pattern.Length; i++)
            patternSet.Add(pattern[i]);
 
        // Build modified string (string with characters
        // only from pattern are taken)
        StringBuilder modifiedString = new StringBuilder(str);
        for (int i = str.Length - 1; i >= 0; i--)
            if (!patternSet.Contains(modifiedString[i]))
                modifiedString.Remove(i, 1);
 
        // Remove more than one consecutive occurrences of pattern
        // characters from modified string.
        for (int i = modifiedString.Length - 1; i > 0; i--)
            if (modifiedString[i] == modifiedString[i - 1])
                modifiedString.Remove(i, 1);
 
        // After above modifications, the length of modified string
        // must be same as pattern length
        if (pattern.Length != modifiedString.Length)
            return false;
 
        // And pattern characters must also be same
        // as modified string characters
        for (int i = 0; i < pattern.Length; i++)
            if (pattern[i] != modifiedString[i])
                return false;
 
        return true;
    }
 
    // Driver program
    public static void Main(String[] args)
    {
        String str = "engineers rock";
        String pattern = "er";
        Console.WriteLine("Expected: true, Actual: " +
                        followsPattern(str, pattern));
 
        str = "engineers rock";
        pattern = "egr";
        Console.WriteLine("Expected: false, Actual: " +
                        followsPattern(str, pattern));
 
        str = "engineers rock";
        pattern = "gsr";
        Console.WriteLine("Expected: false, Actual: " +
                        followsPattern(str, pattern));
 
        str = "engineers rock";
        pattern = "eger";
        Console.WriteLine("Expected: true, Actual: " +
                        followsPattern(str, pattern));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
// Javascript program to check if characters of a string follow
// pattern defined by given pattern.
 
function followsPattern(str, pattern)
{
    // Insert all characters of pattern in a hash set,
        let patternSet = new Set();
        for (let i=0; i<pattern.length; i++)
            patternSet.add(pattern[i]);
   
        // Build modified string (string with characters only from
        // pattern are taken)
        let modifiedString = (str).split("");
        for (let i=str.length-1; i>=0; i--)
            if (!patternSet.has(modifiedString[i]))
                modifiedString.splice(i,1);
   
        // Remove more than one consecutive occurrences of pattern
        // characters from modified string.
        for (let i=modifiedString.length-1; i>0; i--)
            if (modifiedString[i] == modifiedString[i-1])
                modifiedString.splice(i,1);
   
        // After above modifications, the length of modified string
        // must be same as pattern length
        if (pattern.length != modifiedString.length)
            return false;
   
        // And pattern characters must also be same as modified string
        // characters
        for (let i=0; i<pattern.length; i++)
            if (pattern[i] != modifiedString[i])
                return false;
   
        return true;
}
 
// Driver program
let str = "engineers rock";
let pattern = "er";
document.write("Expected: true, Actual: " +
                   followsPattern(str, pattern)+"<br>");
 
str = "engineers rock";
pattern = "egr";
document.write("Expected: false, Actual: " +
                   followsPattern(str, pattern)+"<br>");
 
str = "engineers rock";
pattern = "gsr";
document.write("Expected: false, Actual: " +
                   followsPattern(str, pattern)+"<br>");
 
str = "engineers rock";
pattern = "eger";
document.write("Expected: true, Actual: " +
                   followsPattern(str, pattern)+"<br>");
 
// This code is contributed by rag2127
</script>

Producción: 
 

Expected: true, Actual: true
Expected: false, Actual: false
Expected: false, Actual: false
Expected: true, Actual: true

Complejidad de tiempo: la complejidad de tiempo de las implementaciones anteriores es en realidad O(mn + n^2) ya que usamos deleteCharAt() para eliminar caracteres. Podemos optimizar la solución anterior para trabajar en tiempo lineal. En lugar de usar deleteCharAr(), podemos crear una string vacía y agregarle solo los caracteres necesarios.
StringBuilder se utiliza para operar en la string de entrada. Esto se debe a que StringBuilder es mutable, mientras que String es un objeto inmutable. Para crear una nueva string se necesita espacio O(n), por lo que el espacio extra es O(n).
Hemos discutido dos enfoques más para resolver este problema. 
Compruebe si la string sigue el orden de los caracteres definidos por un patrón o no | Conjunto 1  
Comprobar si la string sigue el orden de los caracteres definido por un patrón o no | Conjunto 3
Este artículo es una contribución de Lalit Ramesh Sirsikar. Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.