두 문자열의 공통 문자를 알파벳 순서로 인쇄합니다.
GfG Practice에서 사용해 보세요. 
산출
두 개의 문자열이 주어지면 다음의 모든 공통 문자가 인쇄됩니다. 사전식 주문하다. 공통 문자가 없으면 -1을 인쇄합니다. 모든 문자는 소문자입니다.
예:
Input : string1 : geeks string2 : forgeeks Output : eegks Explanation: The letters that are common between the two strings are e(2 times) k(1 time) and s(1 time). Hence the lexicographical output is 'eegks' Input : string1 : hhhhhello string2 : gfghhmh Output : hhh
아이디어는 문자 수 배열을 사용하는 것입니다.
- 첫 번째 및 두 번째 문자열에서 'a'부터 'z'까지 모든 문자의 발생 횟수를 셉니다. 이 개수를 두 배열 a1[] 및 a2[]에 저장합니다.
- a1[] 및 a2[]를 탐색합니다(둘 다 메모 크기는 26입니다). 모든 인덱스에 대해 i 문자 'a' + i 횟수는 min(a1[i] a2[i])와 같습니다.
다음은 위 단계의 구현입니다.
C++ // C++ program to print common characters // of two Strings in alphabetical order #include using namespace std ; int main () { string s1 = 'geeksforgeeks' ; string s2 = 'practiceforgeeks' ; // to store the count of // letters in the first string int a1 [ 26 ] = { 0 }; // to store the count of // letters in the second string int a2 [ 26 ] = { 0 }; int i j ; char ch ; char ch1 = 'a' ; int k = ( int ) ch1 m ; // for each letter present increment the count for ( i = 0 ; i < s1 . length () ; i ++ ) { a1 [( int ) s1 [ i ] - k ] ++ ; } for ( i = 0 ; i < s2 . length () ; i ++ ) { a2 [( int ) s2 [ i ] - k ] ++ ; } for ( i = 0 ; i < 26 ; i ++ ) { // the if condition guarantees that // the element is common that is // a1[i] and a2[i] are both non zero // means that the letter has occurred // at least once in both the strings if ( a1 [ i ] != 0 and a2 [ i ] != 0 ) { // print the letter for a number // of times that is the minimum // of its count in s1 and s2 for ( j = 0 ; j < min ( a1 [ i ] a2 [ i ]) ; j ++ ) { m = k + i ; ch = ( char )( k + i ); cout < < ch ; } } } return 0 ; }
Java // Java program to print common characters // of two Strings in alphabetical order import java.io.* ; import java.util.* ; // Function to find similar characters public class Simstrings { static final int MAX_CHAR = 26 ; static void printCommon ( String s1 String s2 ) { // two arrays of length 26 to store occurrence // of a letters alphabetically for each string int [] a1 = new int [ MAX_CHAR ] ; int [] a2 = new int [ MAX_CHAR ] ; int length1 = s1 . length (); int length2 = s2 . length (); for ( int i = 0 ; i < length1 ; i ++ ) a1 [ s1 . charAt ( i ) - 'a' ] += 1 ; for ( int i = 0 ; i < length2 ; i ++ ) a2 [ s2 . charAt ( i ) - 'a' ] += 1 ; // If a common index is non-zero it means // that the letter corresponding to that // index is common to both strings for ( int i = 0 ; i < MAX_CHAR ; i ++ ) { if ( a1 [ i ] != 0 && a2 [ i ] != 0 ) { // Find the minimum of the occurrence // of the character in both strings and print // the letter that many number of times for ( int j = 0 ; j < Math . min ( a1 [ i ] a2 [ i ] ) ; j ++ ) System . out . print ((( char )( i + 'a' ))); } } } // Driver code public static void main ( String [] args ) throws IOException { String s1 = 'geeksforgeeks' s2 = 'practiceforgeeks' ; printCommon ( s1 s2 ); } }
Python3 # Python3 program to print common characters # of two Strings in alphabetical order # Initializing size of array MAX_CHAR = 26 # Function to find similar characters def printCommon ( s1 s2 ): # two arrays of length 26 to store occurrence # of a letters alphabetically for each string a1 = [ 0 for i in range ( MAX_CHAR )] a2 = [ 0 for i in range ( MAX_CHAR )] length1 = len ( s1 ) length2 = len ( s2 ) for i in range ( 0 length1 ): a1 [ ord ( s1 [ i ]) - ord ( 'a' )] += 1 for i in range ( 0 length2 ): a2 [ ord ( s2 [ i ]) - ord ( 'a' )] += 1 # If a common index is non-zero it means # that the letter corresponding to that # index is common to both strings for i in range ( 0 MAX_CHAR ): if ( a1 [ i ] != 0 and a2 [ i ] != 0 ): # Find the minimum of the occurrence # of the character in both strings and print # the letter that many number of times for j in range ( 0 min ( a1 [ i ] a2 [ i ])): ch = chr ( ord ( 'a' ) + i ) print ( ch end = '' ) # Driver code if __name__ == '__main__' : s1 = 'geeksforgeeks' s2 = 'practiceforgeeks' printCommon ( s1 s2 ); # This Code is contributed by Abhishek Sharma
C# // C# program to print common characters // of two Strings in alphabetical order using System ; // Function to find similar characters public class Simstrings { static int MAX_CHAR = 26 ; static void printCommon ( string s1 string s2 ) { // two arrays of length 26 to store occurrence // of a letters alphabetically for each string int [] a1 = new int [ MAX_CHAR ]; int [] a2 = new int [ MAX_CHAR ]; int length1 = s1 . Length ; int length2 = s2 . Length ; for ( int i = 0 ; i < length1 ; i ++ ) a1 [ s1 [ i ] - 'a' ] += 1 ; for ( int i = 0 ; i < length2 ; i ++ ) a2 [ s2 [ i ] - 'a' ] += 1 ; // If a common index is non-zero it means // that the letter corresponding to that // index is common to both strings for ( int i = 0 ; i < MAX_CHAR ; i ++ ) { if ( a1 [ i ] != 0 && a2 [ i ] != 0 ) { // Find the minimum of the occurrence // of the character in both strings and print // the letter that many number of times for ( int j = 0 ; j < Math . Min ( a1 [ i ] a2 [ i ]) ; j ++ ) Console . Write ((( char )( i + 'a' ))); } } } // Driver code public static void Main () { string s1 = 'geeksforgeeks' s2 = 'practiceforgeeks' ; printCommon ( s1 s2 ); } }
JavaScript < script > // Javascript program to print common characters // of two Strings in alphabetical order let MAX_CHAR = 26 ; // Function to find similar characters function printCommon ( s1 s2 ) { // two arrays of length 26 to store occurrence // of a letters alphabetically for each string let a1 = new Array ( MAX_CHAR ); let a2 = new Array ( MAX_CHAR ); for ( let i = 0 ; i < MAX_CHAR ; i ++ ) { a1 [ i ] = 0 ; a2 [ i ] = 0 ; } let length1 = s1 . length ; let length2 = s2 . length ; for ( let i = 0 ; i < length1 ; i ++ ) a1 [ s1 [ i ]. charCodeAt ( 0 ) - 'a' . charCodeAt ( 0 )] += 1 ; for ( let i = 0 ; i < length2 ; i ++ ) a2 [ s2 [ i ]. charCodeAt ( 0 ) - 'a' . charCodeAt ( 0 )] += 1 ; // If a common index is non-zero it means // that the letter corresponding to that // index is common to both strings for ( let i = 0 ; i < MAX_CHAR ; i ++ ) { if ( a1 [ i ] != 0 && a2 [ i ] != 0 ) { // Find the minimum of the occurrence // of the character in both strings and print // the letter that many number of times for ( let j = 0 ; j < Math . min ( a1 [ i ] a2 [ i ]) ; j ++ ) document . write (( String . fromCharCode ( i + 'a' . charCodeAt ( 0 )))); } } } // Driver code let s1 = 'geeksforgeeks' s2 = 'practiceforgeeks' ; printCommon ( s1 s2 ); // This code is contributed by avanitrachhadiya2155 < /script>
산출
eeefgkors
시간 복잡도: n = 길이(더 큰 문자열)를 고려하면 이 알고리즘은 다음과 같이 실행됩니다. 에) 복잡성.
보조 공간: O(1).
