Bir giriş dizesi ve bir kalıp verildiğinde, giriş dizesindeki karakterlerin, kalıpta bulunan karakterlerle belirlenen sırayı takip edip etmediği kontrol edilir. Desende yinelenen karakterler olmayacağını varsayalım.
Örnekler:
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.
Bu sorunu çözmek için iki yaklaşımı tartıştık.
Dizenin bir kalıp tarafından tanımlanan karakterlerin sırasını takip edip etmediğini kontrol edin | Set 1
Dizenin bir kalıp tarafından tanımlanan karakterlerin sırasını takip edip etmediğini kontrol edin | 2'yi ayarla
Bu yaklaşımda öncelikle desen karakterlerine bir etiket (veya sıra) atarız. Etiketler artan sırada atanır.
Örneğin 'gsr' modeli aşağıdaki gibi etiketlenmiştir
'g' => 1 's' => 2 'r' => 3
Bu, önce 'g', sonra 's' ve ardından 'r' geleceği anlamına gelir
Desen karakterlerine etiket atadıktan sonra dize karakterlerini yineliyoruz. Geçiş sırasında son ziyaret edilen karakterin etiketini (veya sırasını) takip ederiz. Geçerli karakterin etiketi önceki karakterden küçükse false değerini döndürürüz. Aksi takdirde son etiketi güncelleriz. Eğer tüm karakterler sırayı takip ederse true değerini döndürürüz.
Aşağıda uygulama yer almaktadır
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>
Çıkış
false
Zaman Karmaşıklığı bu programın Açık) sabit ekstra alanla (dizi etiketi sabit boyutta 256'dır).
Yardımcı Alan: O(256).