根据另一个字符串定义的顺序对字符串进行排序-yiteyi-C++库

给定两个字符串（小写字母）、一个模式和一个字符串。任务是根据模式定义的顺序对字符串进行排序。可以假设模式中包含字符串的所有字符，并且模式中的所有字符只出现一次。 例如：

null

Input  : pat = "bca", str = "abc"Output : str = "bca"Input  : pat = "bxyzca", str = "abcabcabc"Output : str = "bbbcccaaa"Input  : pat = "wcyuogmlrdfphitxjakqvzbnes", str = "jcdokai"Output : str = "codijak"

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

方法1： 其思想是首先对str中所有字符的出现次数进行计数，并将这些计数存储在计数数组中。然后从左到右遍历模式，对于每个字符pat[i]，查看它在count数组中出现了多少次，并将这个字符复制到str。下面是上述想法的实施。

实施：

C++

                         // C++ program to sort a string according to the                       
                         // order defined by a pattern string                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                         const                                     int                                     MAX_CHAR = 26;                       
           
                         // Sort str according to the order defined by pattern.                       
                         void                                     sortByPattern(string& str, string pat)                       
                         {                       
                                                 // Create a count array store count of characters in str.                       
                                                 int                                     count[MAX_CHAR] = { 0 };                       
           
                                                 // Count number of occurrences of each character                       
                                                 // in str.                       
                                                 for                                     (                                     int                                     i = 0; i < str.length(); i++)                       
                                                 count[str[i] -                                     'a'                                     ]++;                       
           
                                                 // Traverse the pattern and print every characters                       
                                                 // same number of times as it appears in str. This                       
                                                 // loop takes O(m + n) time where m is length of                       
                                                 // pattern and n is length of str.                       
                                                 int                                     index = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < pat.length(); i++)                       
                                                 for                                     (                                     int                                     j = 0; j < count[pat[i] -                                     'a'                                     ]; j++)                       
                                                 str[index++] = pat[i];                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 string pat =                                     "bca"                                     ;                       
                                                 string str =                                     "abc"                                     ;                       
                                                 sortByPattern(str, pat);                       
                                                 cout << str;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to sort a string according to the                       
                         // order defined by a pattern string                       
           
                         class                                     GFG {                       
           
                                                 static                                     int                                     MAX_CHAR =                                     26                                     ;                       
           
                                                 // Sort str according to the order defined by pattern.                       
                                                 static                                     void                                     sortByPattern(                                     char                                     [] str,                                     char                                     [] pat)                       
                                                 {                       
                                                 // Create a count array stor                       
                                                 // count of characters in str.                       
                                                 int                                     count[] =                                     new                                     int                                     [MAX_CHAR];                       
           
                                                 // Count number of occurrences of                       
                                                 // each character in str.                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < str.length; i++) {                       
                                                 count[str[i] -                                     'a'                                     ]++;                       
                                                 }                       
           
                                                 // Traverse the pattern and print every characters                       
                                                 // same number of times as it appears in str. This                       
                                                 // loop takes O(m + n) time where m is length of                       
                                                 // pattern and n is length of str.                       
                                                 int                                     index =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < pat.length; i++) {                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j < count[pat[i] -                                     'a'                                     ]; j++) {                       
                                                 str[index++] = pat[i];                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 char                                     [] pat =                                     "bca"                                     .toCharArray();                       
                                                 char                                     [] str =                                     "abc"                                     .toCharArray();                       
                                                 sortByPattern(str, pat);                       
                                                 System.out.println(String.valueOf(str));                       
                                                 }                       
                         }                       
           
                         // This code has been contributed by 29AjayKumar                       

Python3

                         # Python3 program to sort a string according to                       
                         # the order defined by a pattern string                       
                         MAX_CHAR                                     =                                     26                       
           
                         # Sort str according to the order defined by pattern.                       
                         def                                     sortByPattern(                                     str                                     , pat):                       
                                   
                                                 global                                     MAX_CHAR                       
                                   
                                                 # Create a count array store count                       
                                                 # of characters in str.                       
                                                 count                                     =                                     [                                     0                                     ]                                     *                                     MAX_CHAR                       
                                   
                                                 # Count number of occurrences of                       
                                                 # each character in str.                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     ,                                     len                                     (                                     str                                     )):                       
                                                 count[                                     ord                                     (                                     str                                     [i])                                     -                                     97                                     ]                                     +                                     =                                     1                       
                                   
                                                 # Traverse the pattern and print every characters                       
                                                 # same number of times as it appears in str. This                       
                                                 # loop takes O(m + n) time where m is length of                       
                                                 # pattern and n is length of str.                       
                                                 index                                     =                                     0                                     ;                       
                                                 str                                     =                                     ""                       
                                   
                                                 for                                     i                                     in                                     range                                     (                                     0                                     ,                                     len                                     (pat)):                       
                                                 j                                     =                                     0                       
                                                 while                                     (j < count[                                     ord                                     (pat[i])                                     -                                     ord                                     (                                     'a'                                     )]):                       
                                                 str                                     +                                     =                                     pat[i]                       
                                                 j                                     =                                     j                                     +                                     1                       
                                                 index                                     +                                     =                                     1                       
                                   
                                                 return                                     str                       
           
                         # Driver code                       
                         pat                                     =                                     "bca"                       
                         str                                     =                                     "abc"                       
                         print                                     (sortByPattern(                                     str                                     , pat))                       
           
                         # This code is contributed by ihritik                       

C#

                         // C# program to sort a string according to the                       
                         // order defined by a pattern string                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 static                                     int                                     MAX_CHAR = 26;                       
           
                                                 // Sort str according to the order defined by pattern.                       
                                                 static                                     void                                     sortByPattern(                                     char                                     [] str,                                     char                                     [] pat)                       
                                                 {                       
                                                 // Create a count array stor                       
                                                 // count of characters in str.                       
                                                 int                                     [] count =                                     new                                     int                                     [MAX_CHAR];                       
           
                                                 // Count number of occurrences of                       
                                                 // each character in str.                       
                                                 for                                     (                                     int                                     i = 0; i < str.Length; i++) {                       
                                                 count[str[i] -                                     'a'                                     ]++;                       
                                                 }                       
           
                                                 // Traverse the pattern and print every characters                       
                                                 // same number of times as it appears in str. This                       
                                                 // loop takes O(m + n) time where m is length of                       
                                                 // pattern and n is length of str.                       
                                                 int                                     index = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < pat.Length; i++) {                       
                                                 for                                     (                                     int                                     j = 0; j < count[pat[i] -                                     'a'                                     ]; j++) {                       
                                                 str[index++] = pat[i];                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 char                                     [] pat =                                     "bca"                                     .ToCharArray();                       
                                                 char                                     [] str =                                     "abc"                                     .ToCharArray();                       
                                                 sortByPattern(str, pat);                       
                                                 Console.WriteLine(String.Join(                                     ""                                     , str));                       
                                                 }                       
                         }                       
           
                         /* This code contributed by PrinciRaj1992 */                       

Javascript

                         <script>                       
                         // Javascript program to sort a string according to the                       
                         // order defined by a pattern string                       
                         let MAX_CHAR = 26;                       
           
                         // Sort str according to the order defined by pattern.                       
                         function                                     sortByPattern(str,pat)                       
                         {                       
                                                 // Create a count array stor                       
                                                 // count of characters in str.                       
                                                 let count =                                     new                                     Array(MAX_CHAR);                       
                                                 for                                     (let i = 0; i < MAX_CHAR; i++)                       
                                                 {                       
                                                 count[i] = 0;                       
                                                 }                       
                                   
                                                 // Count number of occurrences of                       
                                                 // each character in str.                       
                                                 for                                     (let i = 0; i < str.length; i++) {                       
                                                 count[str[i].charCodeAt(0) -                                     'a'                                     .charCodeAt(0)]++;                       
                                                 }                       
                                   
                                                 // Traverse the pattern and print every characters                       
                                                 // same number of times as it appears in str. This                       
                                                 // loop takes O(m + n) time where m is length of                       
                                                 // pattern and n is length of str.                       
                                                 let index = 0;                       
                                                 for                                     (let i = 0; i < pat.length; i++) {                       
                                                 for                                     (let j = 0; j < count[pat[i].charCodeAt(0) -                                     'a'                                     .charCodeAt(0)]; j++) {                       
                                                 str[index++] = pat[i];                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         let pat =                                     "bca"                                     .split(                                     ""                                     );                       
                         let str =                                     "abc"                                     .split(                                     ""                                     );                       
                         sortByPattern(str, pat);                       
                         document.write((str).join(                                     ""                                     ));                       
           
                         // This code is contributed by rag2127                       
                         </script>                       

输出

bca

时间复杂性： O（m+n），其中m是图案的长度，n是str的长度。

方法2： 使用STL

在C++中，我们可以将一个比较器传递给SORT（）函数，并根据该模式对字符串进行排序。

C++

                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Declaring a vector globally that stores which character                       
                         // is occuring first                       
                         vector<                                     int                                     > position(26, -1);                       
           
                         //Comparator function                       
                         bool                                     cmp(                                     char                                     & char1,                                     char                                     & char2)                       
                         {                       
                                                 return                                     position[char1 -                                     'a'                                     ] < position[char2 -                                     'a'                                     ];                       
                         }                       
           
                         int                                     main()                       
                         {                       
           
                                                 // Pattern                       
                                                 string pat =                                     "wcyuogmlrdfphitxjakqvzbnes"                                     ;                       
           
                                                 for                                     (                                     int                                     i = 0; i < pat.length(); i++) {                       
                                                 if                                     (position[pat[i] -                                     'a'                                     ] == -1)                       
                                                 position[pat[i] -                                     'a'                                     ] = i;                       
                                                 }                       
           
                                                 // String to be sorted                       
                                                 string str =                                     "jcdokai"                                     ;                       
           
                                                 // Passing a comparator to sort function                       
                                                 sort(str.begin(), str.end(), cmp);                       
                                                 cout << str;                       
                         }                       

输出

codijak

运动假定上述模式具有STR的所有字符。考虑修改的版本，其中模式可能不具有所有字符，并且任务是在结尾处放置所有剩余字符（在字符串中，而不是在模式中）。剩下的字符需要按字母顺序排列。提示：在第二个循环中，当增加索引并将字符放入str时，我们也可以减少此时的计数。最后，我们遍历count数组，将剩余的字符按字母顺序排列。

本文由 桑杰·哈达 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章