检查字符串是否遵循模式定义的字符顺序|集合3-yiteyi-C++库

给定一个输入字符串和一个模式，检查输入字符串中的字符是否遵循由模式中的字符确定的相同顺序。假设模式中没有任何重复字符。 例如：

null

Input: string = "engineers rock", pattern = "er";Output: trueAll 'e' in the input string are before all 'r'.Input: string = "engineers rock", pattern = "egr";Output: falseThere are two 'e' after 'g' in the input string.Input: string = "engineers rock", pattern = "gsr";Output: falseThere are one 'r' before 's' in the input string.

我们讨论了解决这个问题的两种方法。检查字符串是否遵循模式定义的字符顺序|集1 检查字符串是否遵循模式定义的字符顺序|集合2

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

在这种方法中，我们首先为模式的字符指定一个标签（或顺序）。标签按递增顺序分配。例如，模式“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 <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         const                                     int                                     CHAR_SIZE = 256;                       
           
                         // Returns true if characters of str follow                       
                         // order defined by a given ptr.                       
                         bool                                     checkPattern(string str, string pat)                       
                         {                       
                                                 // Initialize all orders as -1                       
                                                 vector<                                     int                                     > label(CHAR_SIZE, -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                       
                         int                                     main()                       
                         {                       
                                                 string str =                                     "engineers rock"                                     ;                       
                                                 string pattern =                                     "gsr"                                     ;                       
           
                                                 cout << boolalpha << checkPattern(str, pattern);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // 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

                         # 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#

                         // 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                       

Javascript

                         <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(str,pat)                       
                         {                       
                                                 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

该程序的时间复杂度为O（n），额外空间恒定（数组标签大小恒定，256）。本文由 穆罕默德·伊夫特哈鲁尔·伊斯拉姆·鲁帕姆 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章