차례
문제 정책
이 문제에서 우리는 현. 우리는 모든 문자열에서 공통적 인 문자를 찾아야합니다. 한 문자가 모든 문자열에 여러 번 존재하는 경우 문자를 여러 번 출력해야합니다.
문자열 배열이 있다고 가정 해 보겠습니다.
[ "bella", "label", "roller"]
문자 'e'는 모든 문자열에 한 번 존재하고 l은 모든 문자열에 두 번 존재한다는 것을 알 수 있습니다. 다른 캐릭터는 일반적이지 않습니다.
따라서 출력 목록에서 문자 'e'는 한 번, 문자 'l'은 두 번 나타납니다.
예
["bella","label","roller"]
["e","l","l"]
["cool","lock","cook"]
["c","o"]
접근
여기서 모든 문자열에서 문자 az의 공통 빈도를 찾아야한다는 것을 알 수 있습니다.
모든 문자열에 대해 문자 빈도가 az 인 크기 26의 개수 배열을 만들 수 있습니다. 인덱스 0은 해당 문자열에서 'a'의 개수를 가지며 인덱스 1에는 'b'의 개수가 있습니다.
이제 a에서 z까지의 각 문자에 대해 위에서 만든 배열에 존재할 수있는 최소 개수를 찾아야합니다. 모든 문자열에서 문자의 최소 존재에 관심이 있기 때문에이 작업을 수행합니다. 즉, 각 문자열에서 공통 문자 만 가져옵니다.
그래서 우리는 먼저 ans를 만들 것입니다 정렬 모든 인덱스가 최대 값으로 설정된 크기 26입니다.
그런 다음 왼쪽에서 오른쪽으로 문자열 배열을 탐색합니다. 각 단계에서 현재 문자열에 대한 개수 배열을 만듭니다. 그런 다음 현재 생성 된 배열을 ans 배열과 비교합니다.
최소값에 관심이 있기 때문에 ans 배열의 각 인덱스는 현재 배열의 값이 해당 인덱스의 ans 배열 값보다 작은 경우에만 수정됩니다.
즉, ans [i]
주어진 목록의 모든 문자열을 탐색 한 후 ans 배열을 사용하여 문자 목록을 만듭니다. 응답 배열에서 인덱스 0의 값은 문자 'a'의 개수를 표시하고 인덱스 1의 값은 인덱스 'b'의 개수를 표시하는 식입니다.
따라서 이런 식으로 a에서 z까지 각 문자의 개수를 사용하여 문자의 출력 배열을 만듭니다.
실시
공통 문자 찾기 Leetcode 솔루션을위한 C ++ 프로그램
#include <iostream>
#include <vector>
using namespace std;
vector<string> commonChars(vector<string>& A) {
int ans[26];
int temp[26];
fill(ans,ans+26,100);
for(string str:A){
fill(temp, temp+26,0);
for(int i=0;i<str.size();i++){
temp[str[i]-'a']++;
}
for(int i=0;i<26;i++){
ans[i]=min(ans[i],temp[i]);
}
}
vector<string>ansChars;
for(int i=0;i<26;i++){
for(int j=0;j<ans[i];j++){
char ch=((char)(i+'a'));
string s(1, ch); //convert char ch to string s
ansChars.push_back(s);
}
}
return ansChars;
}
int main()
{
vector<string>A{"bella","label","roller"};
vector<string>ans = commonChars(A);
for(string str:ans){
cout<<str<<" ";
}
cout<<endl;
}
e l l
공통 문자 찾기 Leetcode 솔루션을위한 Java 프로그램
import java.util.*;
import java.lang.*;
class Solution
{
public static void main(String args[])
{
String[]A={"bella","label","roller"};
List<String>ans=commonChars(A);
for(String str:ans){
System.out.print(str+" ");
}
System.out.println();
}
public static List<String> commonChars(String[] A) {
int[]ans=new int[26];
int[]temp=new int[26];
Arrays.fill(ans,Integer.MAX_VALUE);
for(String str:A){
Arrays.fill(temp,0);
for(int i=0;i<str.length();i++){
temp[str.charAt(i)-'a']++;
}
for(int i=0;i<26;i++){
ans[i]=Math.min(ans[i],temp[i]);
}
}
List<String>ansChars=new ArrayList<String>();
for(int i=0;i<ans.length;i++){
for(int j=0;j<ans[i];j++){
ansChars.add((char)(i+'a')+"");
}
}
return ansChars;
}
}
e l l
공통 문자 찾기 Leetcode 솔루션을위한 복잡성 분석
시간 복잡성
의 위에): 여기서 n은 모든 문자열 길이의 합계입니다.
공간 복잡성
O (1) : 두 개의 배열 ans 및 temp, 각각 크기 26이 사용됩니다. 이것은 일정한 크기의 메모리 일뿐입니다. 따라서 공간 복잡도는 O (1)입니다.
