Dada uma string de entrada e um padrão, verifique se os caracteres na string de entrada seguem a mesma ordem determinada pelos caracteres presentes no padrão. Suponha que não haja caracteres duplicados no padrão.
Exemplos:
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.
Discutimos duas abordagens para resolver esse problema.
Verifique se a string segue a ordem dos caracteres definidos por um padrão ou não | Conjunto 1
Verifique se a string segue a ordem dos caracteres definidos por um padrão ou não | Conjunto 2
senão se java
Nesta abordagem, primeiro atribuímos um rótulo (ou ordem) aos caracteres do padrão. Os rótulos são atribuídos em ordem crescente.
Por exemplo, o padrão 'gsr' é rotulado da seguinte forma
'g' => 1 's' => 2 'r' => 3
Significa que 'g' virá primeiro, depois 's' e depois 'r'
Depois de atribuir rótulos aos caracteres padrão, iteramos através dos caracteres string. Durante a travessia, acompanhamos o rótulo (ou ordem) do último personagem visitado. Se o rótulo do caractere atual for menor que o caractere anterior, retornaremos falso. Caso contrário, atualizamos o último rótulo. Se todos os caracteres seguirem a ordem, retornaremos verdadeiro.
boto3
Abaixo está a implementação
C++// C++ program to find if a string follows order // defined by a given pattern. #include
// Java program to find if a string follows order // defined by a given pattern. class GFG { static int CHAR_SIZE = 256; // Returns true if characters of str follow // order defined by a given ptr. static boolean checkPattern(String str String pat) { int[] label = new int[CHAR_SIZE]; // Initialize all orders as -1 for (int i = 0; i < CHAR_SIZE; i++) label[i] = -1; // Assign an order to pattern characters // according to their appearance in pattern int order = 1; for (int i = 0; i < pat.length(); i++) { // give the pattern characters order label[pat.charAt(i)] = order; // increment the order order++; } // Now one by check if string characters // follow above order int last_order = -1; for (int i = 0; i < str.length(); i++) { if (label[str.charAt(i)] != -1) { // If order of this character is less // than order of previous return false. if (label[str.charAt(i)] < last_order) return false; // Update last_order for next iteration last_order = label[str.charAt(i)]; } } // return that str followed pat return true; } // Driver code public static void main(String[] args) { String str = 'engineers rock'; String pattern = 'gsr'; System.out.println(checkPattern(str pattern)); } } // This code is contributed by // sanjeev2552
# Python3 program to find if a string follows # order defined by a given pattern CHAR_SIZE = 256 # Returns true if characters of str follow # order defined by a given ptr. def checkPattern(Str pat): # Initialize all orders as -1 label = [-1] * CHAR_SIZE # Assign an order to pattern characters # according to their appearance in pattern order = 1 for i in range(len(pat)): # Give the pattern characters order label[ord(pat[i])] = order # Increment the order order += 1 # Now one by one check if string # characters follow above order last_order = -1 for i in range(len(Str)): if (label[ord(Str[i])] != -1): # If order of this character is less # than order of previous return false if (label[ord(Str[i])] < last_order): return False # Update last_order for next iteration last_order = label[ord(Str[i])] # return that str followed pat return True # Driver Code if __name__ == '__main__': Str = 'engineers rock' pattern = 'gsr' print(checkPattern(Str pattern)) # This code is contributed by himanshu77
// C# program to find if a string follows order // defined by a given pattern. using System; class GFG { static int CHAR_SIZE = 256; // Returns true if characters of str follow // order defined by a given ptr. static bool checkPattern(String str String pat) { int[] label = new int[CHAR_SIZE]; // Initialize all orders as -1 for (int i = 0; i < CHAR_SIZE; i++) label[i] = -1; // Assign an order to pattern characters // according to their appearance in pattern int order = 1; for (int i = 0; i < pat.Length; i++) { // give the pattern characters order label[pat[i]] = order; // increment the order order++; } // Now one by check if string characters // follow above order int last_order = -1; for (int i = 0; i < str.Length; i++) { if (label[str[i]] != -1) { // If order of this character is less // than order of previous return false. if (label[str[i]] < last_order) return false; // Update last_order for next iteration last_order = label[str[i]]; } } // return that str followed pat return true; } // Driver code public static void Main(String[] args) { String str = 'engineers rock'; String pattern = 'gsr'; Console.WriteLine(checkPattern(str pattern)); } } // This code is contributed by 29AjayKumar
<script> // Javascript program to find if a string follows order // defined by a given pattern. let CHAR_SIZE = 256; // Returns true if characters of str follow // order defined by a given ptr. function checkPattern(strpat) { let label = new Array(CHAR_SIZE); // Initialize all orders as -1 for (let i = 0; i < CHAR_SIZE; i++) label[i] = -1; // Assign an order to pattern characters // according to their appearance in pattern let order = 1; for (let i = 0; i < pat.length; i++) { // give the pattern characters order label[pat[i].charCodeAt(0)] = order; // increment the order order++; } // Now one by check if string characters // follow above order let last_order = -1; for (let i = 0; i < str.length; i++) { if (label[str[i].charCodeAt(0)] != -1) { // If order of this character is less // than order of previous return false. if (label[str[i].charCodeAt(0)] < last_order) return false; // Update last_order for next iteration last_order = label[str[i].charCodeAt(0)]; } } // return that str followed pat return true; } // Driver code let str = 'engineers rock'; let pattern = 'gsr'; document.write(checkPattern(str pattern)); // This code is contributed by rag2127 </script>
Saída
false
Complexidade de tempo deste programa é Sobre) com espaço extra constante (o rótulo da matriz tem tamanho constante 256).
função chr python
Espaço Auxiliar: O(256).