Daný vstupný reťazec a vzor skontrolujú, či znaky vo vstupnom reťazci majú rovnaké poradie, aké určujú znaky prítomné vo vzore. Predpokladajme, že vo vzore nebudú žiadne duplicitné znaky.
Príklady:
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.
Diskutovali sme o dvoch prístupoch k riešeniu tohto problému.
Skontrolujte, či reťazec nasleduje poradie znakov definovaných vzorom alebo nie | Set 1
Skontrolujte, či reťazec nasleduje poradie znakov definovaných vzorom alebo nie | Súprava 2
V tomto prístupe najprv priradíme označenie (alebo poradie) znakom vzoru. Štítky sa priraďujú v rastúcom poradí.
Napríklad vzor „gsr“ je označený nasledovne
'g' => 1 's' => 2 'r' => 3
Znamená to, že „g“ bude prvé, potom „s“ a potom „r“
Po priradení štítkov k znakom vzoru iterujeme cez reťazcové znaky. Pri prechádzaní sledujeme označenie (alebo poradie) poslednej navštívenej postavy. Ak je označenie aktuálneho znaku menšie ako predchádzajúci znak, vrátime hodnotu false. V opačnom prípade aktualizujeme posledný štítok. Ak všetky znaky dodržia poradie, vrátime hodnotu true.
Nižšie je uvedená implementácia
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>
Výstup
false
Časová zložitosť tohto programu je O(n) s konštantným priestorom navyše (označenie poľa má konštantnú veľkosť 256).
Pomocný priestor: O(256).