Annettu syöttömerkkijono ja kuvio tarkista, noudattavatko merkit syötemerkkijonossa samaa järjestystä kuin kuviossa olevien merkkien määräävät. Oletetaan, että kuviossa ei ole päällekkäisiä merkkejä.
Esimerkkejä:
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.
Olemme keskustelleet kahdesta lähestymistavasta tämän ongelman ratkaisemiseksi.
Tarkista, seuraako merkkijono kuvion määrittelemää merkkijärjestystä vai ei | Sarja 1
Tarkista, seuraako merkkijono kuvion määrittelemää merkkijärjestystä vai ei | Sarja 2
java 8 ominaisuudet
Tässä lähestymistavassa määritämme ensin tunnisteen (tai järjestyksen) kuvion merkeille. Tarrat jaetaan kasvavassa järjestyksessä.
Esimerkiksi kuvio 'gsr' on merkitty seuraavasti
'g' => 1 's' => 2 'r' => 3
Se tarkoittaa, että "g" tulee ensin, sitten "s" ja sitten "r"
Kun olet määrittänyt tunnisteet kuviomerkeille, toistamme merkkijonomerkkejä. Matkan aikana pidämme kirjaa viimeisimmän vieraillun hahmon etiketistä (tai järjestyksestä). Jos nykyisen merkin tunniste on pienempi kuin edellinen merkki, palautetaan epätosi. Muuten päivitämme viimeisimmän etiketin. Jos kaikki merkit noudattavat järjestystä, palautetaan tosi.
kutsu javascript-funktio html:stä
Alla toteutus
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>
Lähtö
false
Aika monimutkaisuus tästä ohjelmasta on O(n) jatkuvalla lisätilalla (taulukon nimi on vakiokoko 256).
css lihavoitu
Aputila: O(256).