logo

두 문자열의 공통 문자를 알파벳 순서로 인쇄합니다.

GfG Practice에서 사용해 보세요. ' title=

두 개의 문자열이 주어지면 다음의 모든 공통 문자가 인쇄됩니다. 사전식 주문하다. 공통 문자가 없으면 -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

아이디어는 문자 수 배열을 사용하는 것입니다. 



  1. 첫 번째 및 두 번째 문자열에서 'a'부터 'z'까지 모든 문자의 발생 횟수를 셉니다. 이 개수를 두 배열 a1[] 및 a2[]에 저장합니다. 
  2. 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(0length1): a1[ord(s1[i]) - ord('a')] += 1 for i in range(0length2): 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(0MAX_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(0min(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(s1s2)  {  // 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).

퀴즈 만들기