入力文字列とパターンを指定すると、入力文字列内の文字が、パターン内に存在する文字によって決定された順序と同じ順序に従っているかどうかがチェックされます。パターン内に重複する文字は存在しないと仮定します。
例:
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.
この問題を解決するための 2 つのアプローチについて説明しました。
文字列がパターンで定義された文字の順序に従っているかどうかを確認します。セット1
文字列がパターンで定義された文字の順序に従っているかどうかを確認します。セット2
このアプローチでは、まずパターンの文字にラベル (または順序) を割り当てます。ラベルは昇順に割り当てられます。
たとえば、パターン「gsr」には次のようにラベルが付けられます。
'g' => 1 's' => 2 'r' => 3
これは、「g」が最初に来て、次に「s」が来て、次に「r」が来ることを意味します。
パターン文字にラベルを割り当てた後、文字列文字を反復処理します。トラバース中、最後に訪問したキャラクターのラベル (または順序) を追跡します。現在の文字のラベルが前の文字より小さい場合は false を返します。それ以外の場合は、最後のラベルを更新します。すべての文字が順序に従っている場合は true を返します。
以下は実装です
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>
出力
false
時間計算量 このプログラムのは の上） 一定の追加スペース付き (配列ラベルのサイズは一定 256)。
補助スペース: O(256)。