连接数组后获得的字典最小字符串-yiteyi-C++库

给定n个字符串，按顺序将它们连接起来，以产生尽可能最小的词典字符串。 例如：

null

Input :  a[] = ["c", "cb", "cba"]Output : cbacbcPossible strings are ccbcba, ccbacb, cbccba, cbcbac, cbacbc and cbaccb. Among all these strings, cbacbc is the lexicographically smallest.Input :  a[] = ["aa", "ab", "aaa"]Output : aaaaaab

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

有人可能会认为，将给定的字符串按字典顺序排序，然后将它们连接起来，可以产生正确的输出。这种方法为[“a”、“ab”、“abc”等输入生成正确的输出。然而，在[“c”、“cb”、“cba”]上应用这种方法会产生错误的输入，因此这种方法是不正确的。正确的方法是使用常规排序算法。当比较两个字符串a和b以决定是否必须交换它们时，不要检查a是否在字典上小于b。相反，检查在a的末尾追加b是否会产生一个按字典顺序排列的较小字符串，或者在b的末尾追加a是否会产生较小的字符串。这种方法之所以有效，是因为我们希望连接的字符串按字典顺序排列，而不是单个字符串按字典顺序排列。

C++

                         // CPP code to find the lexicographically                       
                         // smallest string                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Compares two strings by checking if                       
                         // which of the two concatenations causes                       
                         // lexicographically smaller string.                       
                         bool                                     compare(string a, string b)                       
                         {                       
                                                 return                                     (a+b < b+a);                       
                         }                       
           
                         string lexSmallest(string a[],                                     int                                     n)                       
                         {                       
                                                 // Sort strings using above compare()                       
                                                 sort(a, a+n, compare);                       
           
                                                 // Concatenating sorted strings                       
                                                 string answer =                                     ""                                     ;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 answer += a[i];                       
           
                                                 return                                     answer;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 string a[] = {                                     "c"                                     ,                                     "cb"                                     ,                                     "cba"                                     };                       
                                                 int                                     n =                                     sizeof                                     (a)/                                     sizeof                                     (a[0]);                       
                                                 cout << lexSmallest(a, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java code to find the lexicographically                       
                         // smallest string                       
           
                         class                                     GFG {                       
                                   
                         // function to sort the                       
                         // array of string                       
                         static                                     void                                     sort(String a[],                                     int                                     n)                       
                         {                       
                                   
                                                 //sort the array                       
                                                 for                                     (                                     int                                     i =                                     0                                     ;i < n;i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = i +                                     1                                     ;j < n;j++)                       
                                                 {                       
                                   
                                                 // comparing which of the                       
                                                 // two concatenation causes                       
                                                 // lexicographically smaller                       
                                                 // string                       
                                                 if                                     ((a[i] + a[j]).compareTo(a[j] + a[i]) >                                     0                                     )                       
                                                 {                       
                                                 String s = a[i];                       
                                                 a[i] = a[j];                       
                                                 a[j] = s;                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       
                                   
                         static                                     String lexsmallest(String a[],                                     int                                     n)                       
                         {                       
                                   
                                                 // Sort strings                       
                                                 sort(a,n);                       
           
                                                 // Concatenating sorted strings                       
                                                 String answer =                                     ""                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 answer += a[i];                       
           
                                                 return                                     answer;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String args[])                       
                         {                       
                                                 String a[] = {                                     "c"                                     ,                                     "cb"                                     ,                                     "cba"                                     };                       
                                                 int                                     n =                                     3                                     ;                       
                                                 System.out.println(                                     "lexicographically smallest string = "                       
                                                 + lexsmallest(a, n));                       
           
                         }                       
                         }                       
           
                         // This code is contributed by Arnab Kundu                       

Python 3

                         # Python 3 code to find the lexicographically                       
                         # smallest string                       
                         def                                     lexSmallest(a, n):                       
                                                 # Sort strings using above compare()                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     ,n):                       
                                                 for                                     j                                     in                                     range                                     (i                                     +                                     1                                     ,n):                       
                                                 if                                     (a[i]                                     +                                     a[j]>a[j]                                     +                                     a[i]):                       
                                                 s                                     =                                     a[i]                       
                                                 a[i]                                     =                                     a[j]                       
                                                 a[j]                                     =                                     s                       
           
                                                 # Concatenating sorted strings                       
                                                 answer                                     =                                     ""                       
                                                 for                                     i                                     in                                     range                                     ( n):                       
                                                 answer                                     +                                     =                                     a[i]                       
                                                 return                                     answer                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                   
                                                 a                                     =                                     [                                     "c"                                     ,                                     "cb"                                     ,                                     "cba"                                     ]                       
                                                 n                                     =                                     len                                     (a)                       
                                                 print                                     (lexSmallest(a, n))                       
           
                         # This code is contributed by vibhu karnwal                       
           
           
                                   

C#

                         // C# code to find                       
                         // the lexicographically                       
                         // smallest string                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                         // function to sort the                       
                         // array of string                       
                         static                                     void                                     sort(String []a,                                     int                                     n)                       
                         {                       
                                   
                                                 //sort the array                       
                                                 for                                     (                                     int                                     i = 0;i < n;i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = i + 1;j < n;j++)                       
                                                 {                       
                                   
                                                 // comparing which of the                       
                                                 // two concatenation causes                       
                                                 // lexicographically smaller                       
                                                 // string                       
                                                 if                                     ((a[i] + a[j]).CompareTo(a[j] +                       
                                                 a[i]) > 0)                       
                                                 {                       
                                                 String s = a[i];                       
                                                 a[i] = a[j];                       
                                                 a[j] = s;                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       
                                   
                         static                                     String lexsmallest(String []a,                                     int                                     n)                       
                         {                       
                                   
                                                 // Sort strings                       
                                                 sort(a,n);                       
           
                                                 // Concatenating sorted                       
                                                 // strings                       
                                                 String answer =                                     ""                                     ;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 answer += a[i];                       
           
                                                 return                                     answer;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                                                 String []a = {                                     "c"                                     ,                                     "cb"                                     ,                                     "cba"                                     };                       
                                                 int                                     n = 3;                       
                                                 Console.Write(                                     "lexicographically smallest string = "                       
                                                 + lexsmallest(a, n));                       
           
                         }                       
                         }                       
           
                         // This code is contributed by nitin mittal                       

Javascript

                         <script>                       
                         // Javascript code to find the lexicographically                       
                         // smallest string                       
           
                         // function to sort the                       
                         // array of string                       
                         function                                     sort(a,n)                       
                         {                       
           
                                                 // sort the array                       
                                                 for                                     (let i = 0;i < n;i++)                       
                                                 {                       
                                                 for                                     (let j = i + 1;j < n;j++)                       
                                                 {                       
                                   
                                                 // comparing which of the                       
                                                 // two concatenation causes                       
                                                 // lexicographically smaller                       
                                                 // string                       
                                                 if                                     ((a[i] + a[j])>(a[j] + a[i]) )                       
                                                 {                       
                                                 let s = a[i];                       
                                                 a[i] = a[j];                       
                                                 a[j] = s;                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       
           
           
                         function                                     lexsmallest(a,n)                       
                         {                       
                                                 // Sort strings                       
                                                 sort(a,n);                       
                                   
                                                 // Concatenating sorted strings                       
                                                 let answer =                                     ""                                     ;                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 answer += a[i];                       
                                   
                                                 return                                     answer;                       
                         }                       
           
                         // Driver code                       
                         let a=[                                     "c"                                     ,                                     "cb"                                     ,                                     "cba"                                     ];                       
                         let n = 3;                       
                         document.write(                                     "lexicographically smallest string = "                       
                                                 + lexsmallest(a, n));                       
                                   
                                                 // This code is contributed by rag2127                       
                         </script>                       

输出：

cbacbc

时间复杂性： 上面的代码在O（M*N*logN）中运行，其中N是字符串的数量，M是字符串的最大长度。

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

THE END

技术文章